首页 > 代码库 > UVA12716 GCD XOR 数论数学构造
UVA12716 GCD XOR 数论数学构造
题目给你一个N,让你求 两个数字 A,B,且 A>=B<=N,是的 gcd(A,B) == A^B
N的范围是 3*10^7大的吓人一开始没敢想构造,因为就算构造开的数组也太大了,已经10^7了,后来想了半天在^运算这里也没有想出来什么,所以没办法还是大胆构造吧,构造就去按照他题目的意思来了,构造两个数字 i,j其中j是i的倍数,那么j + i与i的最大公约数肯定是i了,那么(j+i)^i == i这样构造出来的就算满足了,然后再模仿gcd辗转相除的愿意 把它们放在一个数组里计数,这样预处理即可
打好以后又打了一个暴力程序来跑答案,结果都是对的,但是交了超时,因为一开始预处理都给赋值了 long long型,在辗转相除的时候 有个%运算,会导致很慢,所以改成int就对了
#define _CRT_SECURE_NO_WARNINGS /*#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<string> #include<math.h> using namespace std; #define IN freopen("c:\\Users\\nit\\desktop\\input.txt", "r", stdin) #define OUT freopen("c:\\Users\\nit\\desktop\\output.txt", "w", stdout) int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int main() { OUT; int ans[510],k=0; memset(ans,0,sizeof(ans)); for(int i=1;i<500;i++) { for(int b=1;b<=i;b++) { for(int a=b;a<=i;a++) { if((a^b)==gcd(a,b)) ans[i]++; } } printf("%d\t",ans[i]); if(k%10==0)puts(""); k++; } return 0; }*/ #include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<string> #include<math.h> using namespace std; //#define IN freopen("c:\\Users\\nit\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\nit\\desktop\\outpu1t.txt", "w", stdout) #define ll long long #define MAXN 30000000 + 5 ll ans[MAXN]; void init() { for(ll i = 1;i<MAXN;i++) { for(ll j = i;i + j < MAXN;j += i) { if( ((i + j)^j) == i) { int x = j; int y = i + j; for(;x > 0 && y > 0;) { int tmp = x%y; x = y; y = tmp; if((x + y) == i) ans[i + j]++; } } } } for(int i = 2;i<MAXN;i++) ans[i] += ans[i-1]; } int main() { init(); int t; scanf("%d",&t); int Case = 0; while(t--) { int n; scanf("%d",&n); printf("Case %d: %lld\n",++Case,ans[n]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。