GCD

链接

GCD

思路

显然，除了素数的整数次幂，其余的数的 值均为 。
对于一个素数 ，则有 。
于是可以考虑在线性筛素数的过程中预处理出 ，这很好预处理，线性筛中记录下每个数 的最小质因数 ,然后对有大于一个质因子的数打上标记。
时间复杂度为 。

代码

#include<bits/stdc++.h>
#define MAXN 10000010
#define ll long long 

using namespace std;

ll v[MAXN],prime[MAXN],m=0,f[MAXN],s[MAXN];
bool vh[MAXN];
void primes(int n) {
    f[1]=1;
    for(int i=2;i<=n;i++) {
        if(!v[i]) {
            v[i]=i;
            f[i]=i;
            prime[++m]=i;
        }
        for(int j=1;j<=m;j++) {
            if(prime[j]>v[i]||prime[j]*i>n) break;
            if(v[i]!=prime[j]||vh[i]) vh[prime[j]*i]=true;
            v[prime[j]*i]=prime[j];
            if(!vh[prime[j]*i]) f[prime[j]*i]=prime[j];
            else f[prime[j]*i]=1;
        }
    }
}

int a,b;

int main() {
    scanf("%d%d",&a,&b);

    primes(b);
    for(int i=1;i<=b;i++) s[i]=s[i-1]+f[i];

    printf("%lld\n",s[b]-s[a-1]);

    return 0;
}