UVA12716 GCD等于XOR GCD XOR
一道数学题。
首先,我们可以知道,a-b>=gcd(a,b)=c;
其次,a-b<=a xor b=c;
综上,可得a-b=c,即a-b=a xor b.
由于范围不大,直接枚举。
第一层枚举c(因为c较少),第二层枚举a,(b=a-c) 再判断c是否等于a^b即可。
#include<bits/stdc++.h> using namespace std; const int N=3e7+7; int n,ans[N]; int main(){ for(int c=1;c<=(N>>1);c++){ for(int a=c<<1,b;a<=N;a+=c){ b=a-c; if((a^b)==c) ans[a]++; } } for(int i=1;i<=N;i++){ ans[i]+=ans[i-1]; } int T,cnt=0; cin>>T; while(T--){ cin>>n; cout<<"Case "<<++cnt<<": "<<ans[n]<<endl; } return 0; }
标签:UVA12716,XOR,GCD,int,枚举,等于 From: https://www.cnblogs.com/DongPD/p/17489865.html