C. Strange Function (思维+数论)-蒲公英云

C. Strange Function (思维+数论)

墨蓝 2022-09-13 06:19 323阅读 0赞

在这里插入图片描述
1 2 3 . . . x − 1 1 \ 2 \ 3 \ … \ x-1 1 2 3 … x−1 是 i i i 的因子， x x x 不是 i i i 的因子

容易得出 l c m ( 1 , 2 , . . . , x − 1 ) lcm(1, 2, …,x-1) lcm(1,2,…,x−1) 是 i i i 的因子，但 l c m ( 1 , 2 , 3… , x − 1 , x ) lcm(1, 2, 3…,x-1, x) lcm(1,2,3…,x−1,x) 不是 i i i 的因子

对于 i i i 贡献的数，这些数的因子包含 1 , 2 , … , i − 1 1,2,…,i-1 1,2,…,i−1的最小公倍数且不包含 i i i 这个因子，因子包含 1 , 2 , … , i − 1 1,2,…,i-1 1,2,…,i−1的最小公倍数的数的个数为 n / l c m ( 1 , 2 , … , i − 1 ) n/lcm(1,2,…,i-1) n/lcm(1,2,…,i−1)，这些数中部包含因子i的个数为 n / l c m ( 1 , 2 , … , i ) n/lcm(1,2,…,i) n/lcm(1,2,…,i)

通过简单的容斥， i i i 的贡献为上述两数之差再乘以 i i i 即可。

题解来源

const int mod = 1e9 + 7;
ll a[50];
ll gcd(ll a, ll b){ return b ? gcd(b,a%b):a;}
void solve()
{ 
    ll n;
    cin >> n;
    a[1] = 1;
    for(int i=2;;i++)
    { 
        a[i] = a[i-1] * i / gcd(a[i-1],i);
        if(a[i] > 1e16+100) break;
    }
    ll res = 0;
    for(int i=2;;i++)
    { 
        ll x = n/a[i-1], y = n/a[i];
        res = (res + i*(x-y))%mod;
        if(!y) break;
    }
    cout << res << endl;
}