首页 > 代码库 > UVa12716 - GCD XOR
UVa12716 - GCD XOR
题意
给一个数n，找出gcd(a,b) = a^b的个数 (1<=b<=a<=n)。
n的数据范围：1到30000000
思路
c满足gcd(a,b) = a^b,打表观察数据得出c = a - b；又因为c是a的约数，用类似素数筛选的方法降低时间复杂度。
总结
敲代码的时候忘记打表这个东西的存在，只要一次性将所有的结果算出存在数组里，每次提取就可以，不用每次都算一遍。
智障啊_(:з」∠)_为什么想不到，不然又可以A一道题
#include <iostream>#include <cstdio>#include <algorithm>#include <map>#include <cstring>#include <string>typedef long long LL;const LL maxn = 30000005;using namespace std;LL ans[maxn];LL T, kase = 0, n;void solve(){ for(int i = 1; i <= maxn; i++) for(int j = i+i; j <= maxn; j+=i) if((j^(j-i)) == i) ans[j]++; for(int i = 2; i <= maxn; i++) ans[i] += ans[i-1];}int main(){ //freopen("in.txt","r",stdin); solve(); cin >> T; while(T--) { cin >> n; cout << "Case " << ++kase << ": " << ans[n] << endl; } return 0;}
UVa12716 - GCD XOR
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。