47 lines
1.3 KiB
C++
47 lines
1.3 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
typedef long long LL;
|
||
//左右边界
|
||
LL l, r;
|
||
int ans;//答案
|
||
const int N = 1e8 + 10;
|
||
const int MOD = 666623333;
|
||
|
||
int primes[N]; //保存的是每一个质数
|
||
int cnt; //cnt代表质数下标,就是到第几个了
|
||
int phi[N]; //欧拉函数值
|
||
bool st[N]; //是不是已经被筛掉了
|
||
// 求1-N之间每一个数的欧拉函数
|
||
// 线性筛法求质数的过程当中，捎带着求出每个数的欧拉函数值,其实还可以顺便求出很多东西。
|
||
void get_eulers(int n) {
|
||
phi[1] = 1;
|
||
for (int i = 2; i <= n; i++) {
|
||
if (!st[i]) {
|
||
primes[cnt++] = i;
|
||
phi[i] = i - 1;
|
||
}
|
||
for (int j = 0; primes[j] <= n / i; j++) {
|
||
int t = primes[j] * i;
|
||
st[t] = true;
|
||
if (i % primes[j] == 0) {
|
||
phi[t] = phi[i] * primes[j];
|
||
break;
|
||
} else {
|
||
phi[t] = phi[i] * (primes[j] - 1);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
//1、读入
|
||
scanf("%lld%lld", &l, &r);
|
||
//2、大力出奇迹！线性筛欧拉函数
|
||
get_eulers(r);
|
||
//3、qiandao(x)=x−ϕ(x)，计算sum,再取一下模
|
||
for (LL i = l; i <= r; i++) ans = (ans + i - phi[i]) % MOD;
|
||
//4、输出答案
|
||
printf("%d\n", ans);
|
||
return 0;
|
||
} |