2 条题解

  • 0
    @ 2025-10-8 17:08:55
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int N = 1e6 + 10;
    LL p[N], v[N], tot;
    bool is_p[N];
    LL n, m;
    LL ans[N];
     
    void Init() {
        v[1] = 1;
        for (int i = 2; i < 100000; ++i) {
            if (!v[i]) {
                v[i] = i;
                p[++tot] = i;
                is_p[i] = 1;
            }
            for (int j = 1; j <= tot; ++j) {
                if (p[j] > v[i] || p[j] * i > 100000) break;
                v[p[j] * i] = p[j];
            }
        }
    }
     
    bool is_prime(LL k) 
    {
        if (k < 100000) return is_p[k];
        for (int i = 1; p[i] * p[i] <= k; ++i) {
            if (k % p[i] == 0) return 0;
        }
         
        return 1;
    }
     
    void Dfs(int pi, LL num, LL cur) {
        if (num == 1) {
            ans[++m] = cur;
            return;
        }
         
        if (num > p[pi] && is_prime(num - 1)) {
            ans[++m] = cur * (num - 1);
        }
         
        for (int i = pi; p[i] * p[i] <= num; ++i) {
            int factor = p[i] + 1, t = p[i];
             
            for (; factor <= num; t *= p[i], factor += t) {
                if (num % factor == 0) {
                    Dfs(i + 1, num / factor, cur * t);
                }
            }
        }
    }
     
    int main() {
        Init();
        while (scanf("%lld", &n) == 1) {
            m = 0;
            memset(ans, 0, sizeof(ans));
            Dfs(1, n, 1);
             
            printf("%lld\n", m);
            sort(ans + 1, ans + m + 1);
            for (int i = 1; i <= m; ++i)printf("%lld ", ans[i]);
            if(m)printf("\n");
        }
        return 0;
    }
    
    • 0
      @ 2025-10-8 17:08:45
      #include <bits/stdc++.h>
      using namespace std;
      typedef long long LL;
      const int N = 1e6 + 10;
      LL p[N], v[N], tot;
      bool is_p[N];
      LL n, m;
      LL ans[N];
       
      void Init() {
          v[1] = 1;
          for (int i = 2; i < 100000; ++i) {
              if (!v[i]) {
                  v[i] = i;
                  p[++tot] = i;
                  is_p[i] = 1;
              }
              for (int j = 1; j <= tot; ++j) {
                  if (p[j] > v[i] || p[j] * i > 100000) break;
                  v[p[j] * i] = p[j];
              }
          }
      }
       
      bool is_prime(LL k) 
      {
          if (k < 100000) return is_p[k];
          for (int i = 1; p[i] * p[i] <= k; ++i) {
              if (k % p[i] == 0) return 0;
          }
           
          return 1;
      }
       
      void Dfs(int pi, LL num, LL cur) {
          if (num == 1) {
              ans[++m] = cur;
              return;
          }
           
          if (num > p[pi] && is_prime(num - 1)) {
              ans[++m] = cur * (num - 1);
          }
           
          for (int i = pi; p[i] * p[i] <= num; ++i) {
              int factor = p[i] + 1, t = p[i];
               
              for (; factor <= num; t *= p[i], factor += t) {
                  if (num % factor == 0) {
                      Dfs(i + 1, num / factor, cur * t);
                  }
              }
          }
      }
       
      int main() {
          Init();
          while (scanf("%lld", &n) == 1) {
              m = 0;
              memset(ans, 0, sizeof(ans));
              Dfs(1, n, 1);
               
              printf("%lld\n", m);
              sort(ans + 1, ans + m + 1);
              for (int i = 1; i <= m; ++i)printf("%lld ", ans[i]);
              if(m)printf("\n");
          }
          return 0;
      }
      • 1

      信息

      ID
      5294
      时间
      1000ms
      内存
      256MiB
      难度
      10
      标签
      递交数
      2
      已通过
      1
      上传者