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;
}