LibreOJ 6491 「XXOI 2018」简单的最大公约数

水题。过于屑。写来放松身心。

∑1≤i1,i2,…,in≤mgcd(i1,i2,…,in)=∑1≤i1,i2,…,in≤m∑d|gcd(i1,i2,…,in)φ(d)=m∑d=1φ(d)(⌊md⌋)n

然后随手一个杜教筛就没了。
注意 n(n+1)2 可能会炸，正确操作是先除以二再乘。

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const unsigned long long N = 1e11;
const unsigned long long M = 1e11;
const int MX = 1e7;
unsigned long long n,m,ans;
inline unsigned long long fpow(unsigned long long a,unsigned long long b)
{
    unsigned long long ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret *= a),a *= a;
    return ret;
}
int vis[MX + 5],cnt,prime[MX + 5];
unsigned long long phi[MX + 5];
unsigned long long mem[MX + 5];
inline int id(unsigned long long x)
{
    return n / x;
}
unsigned long long calc(unsigned long long n)
{
    if(n <= MX)
        return phi[n];
    if(~mem[id(n)])
        return mem[id(n)];
    unsigned long long ret = (n & 1) ? ((n + 1 >> 1) * n) : ((n >> 1) * (n + 1));
    for(register unsigned long long l = 2,r;l <= n;l = r + 1)
    {
        r = n / (n / l);
        ret -= (r - l + 1) * calc(n / l);
    }
    return mem[id(n)] = ret;
}
int main()
{
    memset(mem,-1,sizeof mem),phi[1] = 1;
    for(register int i = 2;i <= MX;++i)
    {
        if(!vis[i])
            phi[prime[++cnt] = i] = i - 1;
        for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
        {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
        phi[i] += phi[i - 1];
    }
    scanf("%llu%llu",&n,&m);
    for(register unsigned long long l = 1,r;l <= m;l = r + 1)
    {
        r = m / (m / l);
        ans += (calc(r) - calc(l - 1)) * fpow(m / l,n);
    }
    printf("%llu\n",ans);
}