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

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

Time Limits:  1000 ms  Memory Limits: 262144 KB  Detailed Limits  

Goto ProblemSet

Description

 

Input

Output

 

Sample Input

3

Sample Output

1

 

Data Constraint

 

做法：，因为???? = ????时肯定无解，我们不妨设???? > ????。 那么有gcd(????, ????) ≤ ???? − ????, ???? ???????????? ???? ≥ ???? − ????，很明显有???? = ???? − ????。我们依然 枚举????, ???? = ???? ∗ ????，因为gcd(????, ???? − ????) = ????，所以我们只需判断???? ???????????? ???? = ???? − ????即 可，时间O(???? log ????)。

 

代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n;
long long ans;

int gcd(int x, int y)
{
    while (y != 0)
    {
        int tmp = x;
        x = y;
        y = tmp % y;    
    }    
    return x;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n / 2 ; i++)
    {
        for (int j = 2; i * j <= n; j++)
            if (i * (j - 1) == (i ^ (i * j))) ans++;
    }
    cout << ans;
}