JZOJ 5376. 【NOIP2017提高A组模拟9.19】Candy 数论

Description
文章图片

Input
文章图片

Output
文章图片

Sample Input 2
2 2 2
4 6 8
Sample Output -1
1
Data Constraint
文章图片

Solution

显然，这三个数在变换中只会越来越接近彼此（即差值越来越小）。
那么设开始时三个数分别为a,b,c(a
当x或y其中一个为奇数，说明a,b,c中出现了奇数，则退出循环。
由于差值的变化都是每次除以2，所以每次将x,y都除以2，直到有奇数。
【JZOJ 5376. 【NOIP2017提高A组模拟9.19】Candy】这样每有一个2因子，则可以“分享”一次，且最多不会超过logN次。

Code

#include #include using namespace std; inline long long read() { long long X=0,w=1; char ch=0; while(ch<'0' || ch>'9') {if(ch=='-') w=-1; ch=getchar(); } while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar(); return X*w; } int main() { int T=read(); while(T--) { long long a=read(),b=read(),c=read(),ans=0; if(a==b && b==c) { printf("-1\n"); continue; } if(a&1) { printf("0\n"); continue; } if(a>b) swap(a,b); if(a>c) swap(a,c); if(b>c) swap(b,c); long long x=b-a,y=c-b; for(int i=0; i<65; i++) { if(x&1 || y&1) { printf("%d\n",i); break; } x>>=1; y>>=1; } } return 0; }