JZOJ 5197. 【NOIP2017提高组模拟7.3】C

Description

Input

Output

Sample Input

3

Sample Output

1

Data Constraint

Solution

• 这题我的方法是打表找规律，可以发现答案可用枚举偶数和系数推出。

• 实际上也可以用下式推出答案： Gcd(a,b)≤a−b≤a xor b

Code

#include<cstdio>
using namespace std;
int n,ans;
int main()
{
scanf("%d",&n);
for(int i=3;i<=n;i+=2)
    {
int k=n/i;
for(int j=1;j<=k;j++)
        {
int p=i*j;
if((p^p-j)==j) ans++;
        }
    }
printf("%d",ans);
return 0;
}