| 
 | 
вернуться в форумtl # include <cstdio> # include <iostream> # include <vector> # include <cstring> # include <algorithm> # include <map> # include <string> # include <set> # include <cmath>   using namespace std;   const int M = 1e9 + 7; const int N = 1000001;   int a[N], n, f[N], prime[170], sz; bool used[N];   void get_primes(){     for (int i = 2; i < 1001; i ++){         for (int j = i + i; j < 1001; j += i) used[j] = true;     }     for (int i = 2; i < 1001; i ++){         if (!used[i]) prime[sz++] = i;     } }   int main(){       scanf("%d", &n);     get_primes();       f[1] = f[2] = 1;     for (int i = 3; i <= n; i ++){         f[i] = f[i - 1] + f[i - 2];         if (f[i] >= M) f[i] -= M;     }     for (int i = n; i > 1; i --){         int p = i;         for (int j = 0; j < sz && prime[j] * prime[j] <= p; j ++){             while (p % prime[j] == 0){                 p /= prime[j];                 a[prime[j]] += f[n - i + 1];                 if (a[prime[j]] >= M) a[prime[j]] -= M;             }         }         if (p > 1){             a[p] += f[n - i + 1];             if (a[p] >= M) a[p] -= M;         }     }     long long ans = 1;     for (int i = 1; i <= n; i ++){         ans = (ans * long long((a[i] + 1) % M)) % M;     }     printf("%lld", ans);       return 0; }  |  
  | 
|