C/C++教程

【UVA12716】 GCD等于XOR

本文主要是介绍【UVA12716】 GCD等于XOR，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

GCD等于XOR

题目描述

在这里插入图片描述

输入格式

在这里插入图片描述

输出格式

在这里插入图片描述

题意翻译

输入数据组数t，接下来t行每行给定一个数字n，如样例所示格式输出满足1<=b<=a<=n且gcd(a,b)==a xor b的(a,b)二元组个数。

输入样例

2
7
20000000

输出样例

Case 1: 4
Case 2: 34866117

题意分析

这道题很良心，题目即做法
由题目我们可得出式子：
在这里插入图片描述
用程序实现：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    const int big=30000001;
    int i,j,n,t,a[big];
    cin>>t;
    int tt=big>>1;
	for(i=1;i<=tt;i++)
	 for(j=(i<<1);j<=big;j+=i) 
	  if(j^i==j-i)  
	   a[j]++;
	for(i=2;i<=big;i++) 
	 a[i]=a[i]+a[i-1];
	for(i=1;i<=t;i++)
	{
		cin>>n;
		cout<<"Case 1: "<<i<<endl;
		cout<<"Case 2: "<<a[n];
	}
	return 0;
}

谢谢阅读

这篇关于【UVA12716】 GCD等于XOR的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航