题解 UVA12716 GCD等于XOR GCD XOR

规律题，打表找规律即可发现

a xor b >= a - b >= gcd(a, b)，

如果 a xor b = gcd(a, b) = c 则 c = a - b

枚举倍数c和a判断b即可

但是我主要想讲的是这道题要注意的，就是在跑循环时，一定要注意数组是否越界，比如

int a[maxn];

  scanf("%d",&T);

  for(int i=1;i<=maxn;++i){

          a[i]=i;

      }

这样写会造成你读入的T被覆盖，导致输出超限，因为数组a[maxn]不能存数，所以循环不能跑到maxn

这样写就是对的

int a[maxn];

  for(int i=1;i<=maxn;++i){

          a[i]=i;

      }

  scanf("%d",&T);

由于你的T是后面读入的，所以不造成影响。

所以各位csper们，要注意预处理千万不要越界！

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=30000010;

long long ans[maxn+10];//保证不越界

int T,n;

int main(){

    for(int c=1;c<=maxn;++c){

        for(int a=c*2;a<=maxn;a+=c){

            int b=a-c;

            if((a^b)==c) ans[a]++;

        }

    }

    for(int i=1;i<=maxn;++i){

        ans[i]+=ans[i-1];

    }

    scanf("%d",&T);

    for(int i=1;i<=T;++i){

        scanf("%d",&n);

        printf("Case %d: %d\n",i,ans[n]);

    }

    return 0;

}

巴特西

题解 UVA12716 GCD等于XOR GCD XOR

最新文章

热门文章