【题目链接】

题目意思

T组案例，给一个n，根据下面的代码求cnt.

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j < i; j++)
    {
        if (gcd(i + j, i - j) == 1)
            cnt++;
    }
}

Sample Input
4
978
438
233
666

Sample Output
194041
38951
11065
89963

解题思路

看题目第一想法，肯定和欧拉函数有关，先打个表，丢到oeis，找不到，把它当成前缀和再打一个表，oeis又找不到，然后队友机智的把第一项换成1，找到了。。。

即对于每个 i, 求有多少个小于它的 a 满足 gcd(i,a) = 1 且 a 是奇数. 当 i 是奇数时, 答案为 phi(i) 2 . 当 i 是偶数时, 答案为 phi(i). 注意 i = 1 时, 答案为 0. 记个前缀和就好了, 复杂度为 O(N + T).

分享两个公式。

AC代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 4e7+5;
bool check[maxn];
int phi[maxn], Prime[maxn];
long long a[20000010];
void init(int MAXN) 
{
    int N = maxn - 1;
    memset(check, false, sizeof(check));
    phi[1] = 1;
    int tot = 0;
    for (int i = 2; i <= N; ++i) {
        if (!check[i]) {
            Prime[tot++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < tot; ++j) {
            if (i*Prime[j] > N) break;
            check[i*Prime[j]] = true;
            if (i%Prime[j] == 0) {
                phi[i*Prime[j]] = phi[i] * Prime[j];
                break;
            }
            else {
                phi[i*Prime[j]] = phi[i] * (Prime[j] - 1);
            }
        }
    }
}
int main()
{
    init(maxn);
    a[1] = 0;
    /* for(int i = 2;i < 20000005;i++){ if(i%2) a[i] = a[i-1]+phi[i]/2; else a[i] = a[i-1]+phi[i]; } */
    for (int i = 2; i < 20000005; i++)
    {
        a[i] = ceil(phi[2 * i] / 2);
        a[i] += a[i - 1];
    }
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        printf("%lld\n", a[n]);
    }
}