网上说高斯消元得到下三角矩阵然后都是phi(i)...反着我是搞不出来

打个表什么的还是能看出来点奇怪的东西，比如后面能整除前面的，然后再乱搞吧2333

 

1 /************************************************************** 2     Problem: 3288 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:304 ms 7     Memory:9596 kb 8 ****************************************************************/ 9  10 #include 
      
       11  12 using namespace std;13 typedef long long ll;14 const int N = 1e6 + 5;15 const int mod = 1e9 + 7;16  17 int n;18 ll ans = 1;19 int phi[N], p[N], cnt;20 bool f[N];21  22 void get_phi(int N) {23     int i, j, k;24     for (phi[1] = 1, i = 2; i <= N; ++i) {25         if (!f[i]) p[++cnt] = i, phi[i] = i - 1;26         for (j = 1; j <= cnt; ++j) {27             if ((k = i * p[j]) > N) break;28             f[k] = 1;29             if (i % p[j] == 0) {30                 phi[k] = phi[i] * p[j];31                 break;32             }33             phi[k] = phi[i] * (p[j] - 1);34         }35     }36 }37  38 int main() {39     int i;40     scanf("%d", &n);41     get_phi(n);42     for (i = 1; i <= n; ++i)43         (ans *= phi[i]) %= mod;44     printf("%lld\n", ans);45     return 0;46 }