526互联

UVA12716 GCD等于XOR GCD XOR

发布时间 2023-06-18 22:01:29作者: DPD

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;
}