PVHOI 5 bài 3 - Kế hoạch luyện tập (60 điểm)

Xem dạng PDF

Gửi bài giải


Điểm: 2,00 (OI)
Giới hạn thời gian: 2.25s
Giới hạn bộ nhớ: 512M
Input: geometric.inp
Output: geometric.out

Tác giả:
Nguồn bài:
PVHOI 5
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Input

Output

Sample Input 1

2
13 15

Sample Output 1

7 8

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -2
    dtnguyenthehung  đã bình luận lúc 20, Tháng 4, 2025, 3:15

    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> 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 */


    • -3
      dtnguyenthehung  đã bình luận lúc 20, Tháng 4, 2025, 3:16

      code nha mọi người


  • 0
    tranbaphu098  đã bình luận lúc 16, Tháng 4, 2025, 11:58

    ai bt ko chỉ tui vs


    • -4
      dtnguyenthehung  đã bình luận lúc 20, Tháng 4, 2025, 3:16

      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> 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 */


  • 0
    doanhdung2k11  đã bình luận lúc 3, Tháng 4, 2025, 10:16

    ...


  • 2
    skyvn97  đã bình luận lúc 4, Tháng 3, 2025, 15:57

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


  • -1
    arnold11022009  đã bình luận lúc 7, Tháng 2, 2025, 13:58

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