「题解」CME

爆炸oj.png……

一 题目

Source

Descriptions

Let’s denote correct match equation (we will denote it as CME) an equation a+b=c there all integers a, b and c are greater than zero.
For example, equations 2+2=4 (||+||=||||) and 1+2=3 (|+||=|||) are CME but equations 1+2=4 (|+||=||||), 2+2=3 (||+||=|||), and 0+1=1 (+|=|) are not.

Now, you have n matches. You want to assemble a CME using all your matches. Unfortunately, it is possible that you can’t assemble the CME using all matches. But you can buy some extra matches and then assemble CME!
For example, if n=2, you can buy two matches and assemble |+|=||, and if n=5 you can buy one match and assemble ||+|=|||.

Calculate the minimum number of matches which you have to buy for assembling CME.
Note, that you have to answer q independent queries.

Input

The first line contains one integer q (1≤q≤100) — the number of queries.
The only line of each query contains one integer n (2≤n≤109) — the number of matches.

Output

For each test case print one integer in single line — the minimum number of matches which you have to buy for assembling CME.

---

二 题解

简化一下题面：给定 n ，设 a+b+c = n+r。求得最小的 r ，使得 a+b = c。
用 c 代式一里面的 a+b ，则 2c = n+r。即 2c-r = n，n 是已知的，于是这个东西看起来很像exgcd。

实际上不需要exgcd，这个不定方程总有特解：c = 0, r = -n。根据一堆奇奇怪怪的东西我们得到：c在对(-1/gcd(2,-1))取模意义下定义，b在对(2/gcd(2,-1))取模意义下定义。
即c ≡ 0 (mod 1), r ≡ -n (mod -2)。

然后再回想一下 c 和 r 实际上是有取值范围的，因为 a,b ⩾ 1，所以 c ⩾ 2，并且有 r ⩾ 0。

然后不动脑子你就可以写出这样一个 while ：

int c = 0,r = -n,cnt;
while(c<2 || r<0){
    c += 1; r += 2;
}

然后输出 r 就好了，但是可惜它跑得不够快。

然后动一动脑子你就会发现上面那个 while 可以直接作除法来解决，就是这样：

int c = 0,r = -n,cnt;
if(!(n % 2)){
    cnt = n/2; r = 0;
}
else{
    cnt = (n/2) + 1; r = 1;
}
if(c+cnt < 2){
    int k = 2 - c - cnt;
    r += 2*k;
}

然后就做完了。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
 
int q,n;
 
int main()
{
    scanf("%d",&q);
    while(q--){
        scanf("%d",&n);
        int c = 0,r = -n,cnt;
        /*
        while(c<2 || r<0){
            c += 1; r += 2;
        }
        */
        if(!(n % 2)){
            cnt = n/2; r = 0;
        }
        else{
            cnt = (n/2) + 1; r = 1;
        }
        if(c+cnt < 2){
            int k = 2 - c - cnt;
            r += 2*k;
        }
        printf("%d\n",r);
    }
    return 0;
}