Comments

• 
  

  -12

  

  dtnguyenthehung  commented on April 20, 2025, 3:15 a.m.

  include<bits/stdc++.h>

  define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)

  define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)

  define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)

  define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)

  define ALL(v) (v).begin(), (v).end()

  define fi first

  define se second

  define MASK(i) (1LL << (i))

  define BIT(x, i) (((x) >> (i)) & 1)

  define div _div

  define next _next

  define prev _prev

  define left _left

  define right _right

  define _builtinpopcount _builtinpopcountll

  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); }

  /* Author: Van Hanh Pham */

  /* END OF TEMPLATE - ACTUAL SOLUTION COMES HERE */

  define MAX 20002000

  define SQRT 4545

  define LENGTH 25

  const int MOD = (int)1e9 + 22071997;

  int result[MAX + 3], pw[SQRT + 3][LENGTH + 3]; bool coprime[SQRT + 3][SQRT + 3]; int primeDiv[MAX + 3]; long long savedResult[MAX + 3];

  int getPw(int x, int k) { if (k == 0) return 1; if (k == 1) return x; return x > SQRT ? MAX + 1 : pw[x][k]; }

  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; }

  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;

  FOR(i, 1, SQRT) FOR(j, 1, SQRT) coprime[i][j] = true;
  FOR(i, 2, SQRT) if (primeDiv[i] == i)
      for (int j = i; j <= SQRT; j += i) for (int k = i; k <= SQRT; k += i) coprime[j][k] = false;
  
  FOR(i, 1, SQRT) {
      pw[i][0] = 1;
      FOR(j, 1, LENGTH) pw[i][j] = min(1LL * MAX, 1LL * pw[i][j - 1] * i);
  }
  
  FOR(k, 2, LENGTH) FOR(q, 1, SQRT) {
      if (pw[q][k] >= MAX) break;
      FOR(p, q + 1, SQRT) {
          int sum = getSum(p, q, k);
  
          if (sum >= MAX) break;
          if (!coprime[p][q]) continue;
          result[sum]++;
      }
  }
  

  }

  vector<pair<int, int>> factors; void backtrack(int pos, int val, long long &sum) { if ((int)pos >= factors.size()) { sum += result[val]; return; }

  int tmp = val, pr = factors[pos].fi;
  FOR(i, 0, factors[pos].se) {
      backtrack(pos + 1, tmp, sum);
      if (i < factors[pos].se) tmp *= pr;
  }
  

  }

  int solve(int n) { if (n < 3) return 0;

  long long &res = savedResult[n];
  if (res > 0) return res;
  
  res = n % 2 == 0 ? n / 2 - 1 : n / 2;
  
  factors.clear();
  while (n > 1) {
      int p = primeDiv[n];
      factors.push_back(make_pair(p, 0));
      while (n % p == 0) {
          factors.back().se++;
          n /= p;
      }
  }
  
  backtrack(0, 1, res);
  
  return res % MOD;
  

  }

  int main(void) {

  ifdef ONLINE_JUDGE

  freopen("geometric.inp", "r", stdin);
  freopen("geometric.out", "w", stdout);
  

  endif // ONLINE_JUDGE

  prepare();
  
  int input; scanf("%d", &input);
  while (scanf("%d", &input) == 1) printf("%d ", solve(input)); printf("\n");
  return 0;
  

  }

  /* LOOK AT MY CODE. MY CODE IS AMAZING :D */

  This comment is hidden due to too much negative feedback. Show it anyway.

• 
  

  -9

  

  dtnguyenthehung  commented on April 20, 2025, 3:16 a.m.

  code nha mọi người

  This comment is hidden due to too much negative feedback. Show it anyway.

• 
  

  0

  

  tranbaphu098  commented on April 16, 2025, 11:58 a.m.

  ai bt ko chỉ tui vs

• 
  

  -10

  

  dtnguyenthehung  commented on April 20, 2025, 3:16 a.m.

  include<bits/stdc++.h>

  define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)

  define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)

  define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)

  define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)

  define ALL(v) (v).begin(), (v).end()

  define fi first

  define se second

  define MASK(i) (1LL << (i))

  define BIT(x, i) (((x) >> (i)) & 1)

  define div _div

  define next _next

  define prev _prev

  define left _left

  define right _right

  define _builtinpopcount _builtinpopcountll

  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); }

  /* Author: Van Hanh Pham */

  /* END OF TEMPLATE - ACTUAL SOLUTION COMES HERE */

  define MAX 20002000

  define SQRT 4545

  define LENGTH 25

  const int MOD = (int)1e9 + 22071997;

  int result[MAX + 3], pw[SQRT + 3][LENGTH + 3]; bool coprime[SQRT + 3][SQRT + 3]; int primeDiv[MAX + 3]; long long savedResult[MAX + 3];

  int getPw(int x, int k) { if (k == 0) return 1; if (k == 1) return x; return x > SQRT ? MAX + 1 : pw[x][k]; }

  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; }

  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;

  FOR(i, 1, SQRT) FOR(j, 1, SQRT) coprime[i][j] = true;
  FOR(i, 2, SQRT) if (primeDiv[i] == i)
      for (int j = i; j <= SQRT; j += i) for (int k = i; k <= SQRT; k += i) coprime[j][k] = false;
  
  FOR(i, 1, SQRT) {
      pw[i][0] = 1;
      FOR(j, 1, LENGTH) pw[i][j] = min(1LL * MAX, 1LL * pw[i][j - 1] * i);
  }
  
  FOR(k, 2, LENGTH) FOR(q, 1, SQRT) {
      if (pw[q][k] >= MAX) break;
      FOR(p, q + 1, SQRT) {
          int sum = getSum(p, q, k);
  
          if (sum >= MAX) break;
          if (!coprime[p][q]) continue;
          result[sum]++;
      }
  }
  

  }

  vector<pair<int, int>> factors; void backtrack(int pos, int val, long long &sum) { if ((int)pos >= factors.size()) { sum += result[val]; return; }

  int tmp = val, pr = factors[pos].fi;
  FOR(i, 0, factors[pos].se) {
      backtrack(pos + 1, tmp, sum);
      if (i < factors[pos].se) tmp *= pr;
  }
  

  }

  int solve(int n) { if (n < 3) return 0;

  long long &res = savedResult[n];
  if (res > 0) return res;
  
  res = n % 2 == 0 ? n / 2 - 1 : n / 2;
  
  factors.clear();
  while (n > 1) {
      int p = primeDiv[n];
      factors.push_back(make_pair(p, 0));
      while (n % p == 0) {
          factors.back().se++;
          n /= p;
      }
  }
  
  backtrack(0, 1, res);
  
  return res % MOD;
  

  }

  int main(void) {

  ifdef ONLINE_JUDGE

  freopen("geometric.inp", "r", stdin);
  freopen("geometric.out", "w", stdout);
  

  endif // ONLINE_JUDGE

  prepare();
  
  int input; scanf("%d", &input);
  while (scanf("%d", &input) == 1) printf("%d ", solve(input)); printf("\n");
  return 0;
  

  }

  /* LOOK AT MY CODE. MY CODE IS AMAZING :D */

  This comment is hidden due to too much negative feedback. Show it anyway.

• 
  

  -1

  

  doanhdung2k11  commented on April 3, 2025, 10:16 a.m.

  ...

• 
  

  2

  

  skyvn97  commented on March 4, 2025, 3:57 p.m.

  Các bạn xem đề bài ở đây nhé: https://oj.vnoi.info/problem/pvh5_a

• 
  

  0

  

  arnold11022009  commented on Feb. 7, 2025, 1:58 p.m.

  đề mình tìm ở đâu v mn

• 
  

  1

  

  ngoccaidu2008  commented on Nov. 1, 2025, 1:29 a.m.

  Ở đây nhé: Đề ở đây