题解 P3601 【签到题】

Jayun · 2020-08-13 18:41:08 · 题解

题目大意：

求 \sum_{i=l}^{r}(i-\varphi(i))\mod 666623333。

正文：

方法一：

预处理出所有的欧拉函数值，直接求 \sum_{i=l}^{r}(i-\varphi(i))\mod 666623333。但是 1\leq l\leq r\leq 10^{12}，只能过 60% 的数据。

方法二：

发现数据 r-l\leq 10^6，这是一个很不错的切入点。为了得到欧拉函数值，先筛出 \sqrt{r}=10^6 内所有质数，统计每个质数对 [l,r] 内所有欧拉函数值的贡献。

法二代码：

ll pri[N], cnt, phi[N], A[N], ans;
bool vis[N];

void Prime ()
{
    for (int i = 2; i <= N - 10; i++)
    {
        if(!vis[i]) pri[++cnt] = i;
        for (int j = 1; j <= cnt && i * pri[j] <= N - 10; j++)
        {
            vis[pri[j] * i] = 1;
            if(!(i % pri[j])) break;
        }
    }
} 

int main()
{
    Prime();
    scanf ("%lld%lld", &l, &r);
    for (ll i = l; i <= r; i++)
        phi[i - l] = i, A[i - l] = i;
    for (int i = 1; i <= cnt && pri[i] * pri[i] <= r; i++)
    {
        ll pr = pri[i], start = l;
        if (l % pr) start = l / pr * pr + pr;
        for (ll j = start; j <= r; j += pr)
        {
            phi[j - l] = phi[j - l] / pr * (pr - 1);
            while(A[j - l] % pr == 0) A[j - l] /= pr;
        }
    } 
    for (ll i = l; i <= r; i++)
    {
        if(A[i - l] > 1)
            phi[i - l] = phi[i - l] / A[i - l] * (A[i - l] - 1);
        ans = (ans + (i - phi[i - l]) % mod) %mod;
    }
    printf ("%lld", ans);
    return 0;
}