P3601 签到题


传送门

思路

欧拉函数+线性筛,除了欧拉函数,还要处理大质数这个细节问题。

代码

#include
#define MAXN 1000007
#define MOD 666623333
using namespace std;
typedef long long LL;
int prime[MAXN], cnt, ans; bool vis[MAXN];
LL phi[MAXN], help[MAXN], Left, Right;
int main(void)
{
    for (int i = 2; i < MAXN; i++)
    {
        if (!vis[i]) prime[++cnt] = i;
        for (int j = 1; j <= cnt && i * prime[j] < MAXN; j++)
        {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
    cin >> Left >> Right;
    for (LL i = Left; i <= Right; i++)
    {
        phi[i - Left + 1] = i;
        help[i - Left + 1] = i;
    }
    for (int i = 1; i<=cnt; i++)
    {
        LL prim = prime[i];
        LL start = (Left - 1) / prim * prim;
        for (LL j = start + prim; j <= Right; j += prim)
        {
            phi[j - Left + 1] = phi[j - Left + 1] / prim * (prim - 1);
            while (help[j - Left + 1] % prim == 0) help[j - Left + 1] /= prim;
        }
    }
    for (LL i = Left; i <= Right; i++)
    {
        if (help[i - Left + 1] > 1)
            phi[i - Left + 1] = phi[i - Left + 1] / help[i - Left + 1] * (help[i - Left + 1] - 1);
        ans = (ans + (i - phi[i - Left + 1]) % MOD) % MOD;
    }
    cout << ans;
    return 0;
}