题解
考察了素毕达哥拉斯三元组的生成。
貌似没必要加很多的优化？1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int ans1[1000005] = {0}, ans2[1000005] = {0};
bool vis[1000005] = {0};
int n;
int gcd(int a, int b){
return (!b) ? a : gcd(b, a % b);
}
void init(){
for(int v = 2; v <= 1000; ++v){
if(v * v > n)break;
for(int u = (v % 2 == 0) ? 1 : 2; u < v; u += 2){
if(u * u + v * v > n)
break;
if(gcd(v, u) != 1)
continue;
int aa = v * v - u * u, bb = 2 * u * v, cc = v * v + u * u;
ans1[cc]++;
for(int i = 1; i * cc <= n; ++i)
vis[i * aa] = 1,
vis[i * bb] = 1,
vis[i * cc] = 1;
}
}
for(int i = 1; i <= n; ++i)
ans1[i] += ans1[i - 1], ans1[i - 1] = 0,
ans2[i] = ans2[i - 1] + 1 - vis[i], ans2[i - 1] = 0, vis[i] = 0;
}
void solve(){
printf("%d %d\n", ans1[n], ans2[n]);
ans1[n] = ans2[n] = 0;
}
int main(){
while(scanf("%d", &n) == 1){
init();
solve();
}
return 0;
}