给定
首先有一个较为显然的想法,即埃筛
考虑正解,有个妙妙转化,即将原式的
然后考虑处理钦定
于是不难发现
xxxxxxxxxx
531
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22template < typename T = int >
23inline T read(void);
24
25int N;
26ll ans(0);
27
28int main(){
29 N = read();
30 for(int a = 1; a * a <= N; ++a)
31 for(int b = a + 1; b * b <= N; ++b)
32 if(__gcd(a, b) == 1)
33 ans += 2 * (N / (b * b));
34 printf("%lld\n", ans + N);
35 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
36 return 0;
37}
38
39template < typename T >
40inline T read(void){
41 T ret(0);
42 int flag(1);
43 char c = getchar();
44 while(c != '-' && !isdigit(c))c = getchar();
45 if(c == '-')flag = -1, c = getchar();
46 while(isdigit(c)){
47 ret *= 10;
48 ret += int(c - '0');
49 c = getchar();
50 }
51 ret *= flag;
52 return ret;
53}
update-2022_12_06 初稿