uva12716 n以内有多少对整数a、b满足(1≤b≤a)且gcd(a, b) = xor(a, b)

额现在才补==

这题当时是cp各种姿势打表发现的==然后我大胆用了类似筛法写了一下，竟然给过了==

规律：如果gcd(a, b) = xor(a, b) = c， 则 c = a - b

然后就能利用c来筛了

1 #include<stdio.h> 2 #include<string.h> 3 int vis[30000005],sum[30000005]; 4 int main() 5 { 6 int T,i,j,t; 7 memset(vis,0,sizeof(vis)); 8 for (i=1;i<=15000000;i++) 9 for (j=2*i;j<=30000000;j+=i) 10 if ((j^(j-i))==i) vis[j]++; 11 sum[0]=0; 12 for (i=1;i<=30000000;i++) 13 sum[i]=sum[i-1]+vis[i]; 14 scanf("%d",&T); 15 for (t=1;t<=T;t++) 16 { 17 scanf("%d",&i); 18 printf("Case %d: %d\n",t,sum[i]); 19 } 20 }

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=49096

转载于:https://www.cnblogs.com/xiao-xin/articles/4307726.html

总结

以上是生活随笔为你收集整理的uva12716 n以内有多少对整数a、b满足(1≤b≤a)且gcd(a, b) = xor(a, b)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。