fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
  3. #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
  4. #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
  5. #define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
  6. #define ALL(v) (v).begin(), (v).end()
  7. #define fi first
  8. #define se second
  9. #define MASK(i) (1LL << (i))
  10. #define BIT(x, i) (((x) >> (i)) & 1)
  11. #define div _div
  12. #define next _next
  13. #define prev _prev
  14. #define left _left
  15. #define right _right
  16. #define _builtinpopcount _builtinpopcountll
  17. using namespace std; template<class X, class Y> bool minimize(X &x, const Y &y) { X eps = 1e-9; if (x > y + eps) { x = y; return true; } else return false; } template<class X, class Y> bool maximize(X &x, const Y &y) { X eps = 1e-9; if (x + eps < y) { x = y; return true; } else return false; } template<class T> T Abs(const T &x) { return (x < 0 ? -x : x); }
  18.  
  19. /* Author: Van Hanh Pham */
  20.  
  21. /* END OF TEMPLATE - ACTUAL SOLUTION COMES HERE */
  22.  
  23. #define MAX 20002000
  24. #define SQRT 4545
  25. #define LENGTH 25
  26. const int MOD = (int)1e9 + 22071997;
  27.  
  28. int result[MAX + 3], pw[SQRT + 3][LENGTH + 3]; bool coprime[SQRT + 3][SQRT + 3]; int primeDiv[MAX + 3]; long long savedResult[MAX + 3];
  29.  
  30. int getPw(int x, int k) { if (k == 0) return 1; if (k == 1) return x; return x > SQRT ? MAX + 1 : pw[x][k]; }
  31.  
  32. int getSum(int p, int q, int k) { long long res = 0; REP(i, k + 1) { res += 1LL * getPw(p, i) * getPw(q, k - i); if (res > MAX) return MAX; } return res; }
  33.  
  34. void prepare(void) { REP(i, 2) primeDiv[i] = -1; for (int i = 2; i * i <= MAX; i++) if (primeDiv[i] == 0) for (int j = i * i; j <= MAX; j += i) primeDiv[j] = i; FOR(i, 2, MAX) if (primeDiv[i] == 0) primeDiv[i] = i;
  35. FOR(i, 1, SQRT) FOR(j, 1, SQRT) coprime[i][j] = true;
  36. FOR(i, 2, SQRT) if (primeDiv[i] == i)
  37.     for (int j = i; j <= SQRT; j += i) for (int k = i; k <= SQRT; k += i) coprime[j][k] = false;
  38.  
  39. FOR(i, 1, SQRT) {
  40.     pw[i][0] = 1;
  41.     FOR(j, 1, LENGTH) pw[i][j] = min(1LL * MAX, 1LL * pw[i][j - 1] * i);
  42. }
  43.  
  44. FOR(k, 2, LENGTH) FOR(q, 1, SQRT) {
  45.     if (pw[q][k] >= MAX) break;
  46.     FOR(p, q + 1, SQRT) {
  47.         int sum = getSum(p, q, k);
  48.  
  49.         if (sum >= MAX) break;
  50.         if (!coprime[p][q]) continue;
  51.         result[sum]++;
  52.     }
  53. }
  54. }
  55.  
  56. vector<pair<int, int>> factors; void backtrack(int pos, int val, long long &sum) { if ((int)pos >= factors.size()) { sum += result[val]; return; }
  57. int tmp = val, pr = factors[pos].fi;
  58. FOR(i, 0, factors[pos].se) {
  59.     backtrack(pos + 1, tmp, sum);
  60.     if (i < factors[pos].se) tmp *= pr;
  61. }
  62. }
  63.  
  64. int solve(int n) { if (n < 3) return 0;
  65. long long &res = savedResult[n];
  66. if (res > 0) return res;
  67.  
  68. res = n % 2 == 0 ? n / 2 - 1 : n / 2;
  69.  
  70. factors.clear();
  71. while (n > 1) {
  72.     int p = primeDiv[n];
  73.     factors.push_back(make_pair(p, 0));
  74.     while (n % p == 0) {
  75.         factors.back().se++;
  76.         n /= p;
  77.     }
  78. }
  79.  
  80. backtrack(0, 1, res);
  81.  
  82. return res % MOD;
  83.  
  84. }
  85.  
  86. int main() {
  87. freopen("geometric.inp", "r", stdin);
  88. freopen("geometric.out", "w", stdout);
  89. prepare();
  90. int input; scanf("%d", &input);
  91. while (scanf("%d", &input) == 1) printf("%d ", solve(input)); printf("\n");
  92. return 0;
  93. }
Success #stdin #stdout 0.61s 180872KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CCyLQE
language:
C++ (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!