记录编号	454951	评测结果	AAAAAAAAAA
题目名称	[SYOI 2017] ZF与数论	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	2.076 s
提交时间	2017-09-30 15:25:33	内存使用	15.69 MiB

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const ll mod = 998244353;
bitset<maxn> vis;
vector<int> pri;
ll l, r;
ll phi[maxn], num[maxn];
int main()
{
    freopen("ZFAndMath.in","r",stdin);
    freopen("ZFAndMath.out","w",stdout);
    cin >> l >> r;
    for (int i = 2; i < 1e6 + 10; ++i)
    {
        if (!vis[i])
            pri.push_back(i), vis[i] = 1;
        for (int j = 0; j < pri.size(); ++j)
        {
            ll k = i * pri[j];
            if (k > 1e6 + 10) break;
            vis[k] = 1;
            if (i % pri[j] == 0) break;
        }
    }    
    ll phi_sum = 0;
    for (ll i = 0; i <= r - l; ++i) num[i] = phi[i] = l + i;
    for (ll i = 0; i < pri.size(); ++i)
    {
        ll j = pri[i];
        if (j > r) break;
        if (l % j == 0) j *= (l / j);
        else j *= ((l / j) + 1);
        for (ll k = j; k <= r; k += pri[i])
        {
            phi[k - l] /= pri[i], phi[k - l] *= (pri[i] - 1);
            while(num[k - l] % pri[i] == 0) num[k - l] /= pri[i];   
        }
    }
    for (ll i = 0; i <= r - l; ++i)
        if (num[i] != 1)
            phi[i] /= num[i], phi[i] *= (num[i] - 1);
    for (ll i = 0; i <= r - l; ++i) phi_sum += phi[i];
    cout << phi_sum % mod << endl;
}