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
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> #define INF 2000000000 using namespace std; typedef long long ll; int (){ 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 %dn", ans1[n], ans2[n]); ans1[n] = ans2[n] = 0; } int main(){ while(scanf("%d", &n) == 1){ init(); solve(); } return 0; }
|
近期评论