初涉的话先留坑吧
题目大意
$\sum_{i_1}^{a_1}\sum_{i_2}^{a_2}\cdots\sum_{i_m}^{a_m}(i_1,i_2,\cdots,i_m)$
$a_i<=1e6,2=<m<=10$
题目分析
首先寄存两篇比较好的博客：
1.
2.
这个问题可以推广至一类模型：$\sum_{i=1}^n\sum_{j=1}^mf[\gcd(i,j)]$.
该模型的推论是$原式=\sum_{u=1}^{\min(n,m)}\lfloor\frac{n}{u}\rfloor\lfloor\frac{m}{u}\rfloor\sum_{d|u}f[d]\mu(\frac{u}{d})$
注意到在本题中$f=id$，那么也就是说$原式=\sum_{u=1}^{\min(n,m)}\lfloor\frac{n}{u}\rfloor\lfloor\frac{m}{u}\rfloor \varphi(u)$.
因此先一遍线性筛求$\varphi$的前缀和，再数论分块做$\lfloor\frac{n}{u}\rfloor$这一部分。
本题对模型的转化还不算太深（算是比较裸的反演）
1 #include2 typedef long long ll; 3 const int maxn = 13; 4 const int MO = 1e9+7; 5 const int TOP = 1000000; 6 const int maxPri = 80035; 7 const int maxNum = 1000035; 8 9 int T,n,mn,a[maxn],pr[maxPri];10 ll phi[maxNum],ans,tmp;11 bool vis[maxNum];12 13 int read()14 {15 char ch = getchar();16 int num = 0;17 bool fl = 0;18 for (; !isdigit(ch); ch=getchar())19 if (ch=='-') fl = 1;20 for (; isdigit(ch); ch=getchar())21 num = (num<<1)+(num<<3)+ch-48;22 if (fl) num = -num;23 return num;24 }25 void init()26 {27 phi[1] = 1;28 for (int i=2; i<=TOP; i++)29 {30 if (!vis[i]) pr[++pr[0]] = i, phi[i] = i-1;31 for (int j=1; (j<=pr[0])&&(pr[j]*i<=TOP); j++)32 {33 vis[pr[j]*i] = 1, phi[pr[j]*i] = phi[i]*pr[j];34 if (i%pr[j]==0) break;35 phi[pr[j]*i] = phi[i]*(pr[j]-1);36 }37 }38 for (int i=2; i<=TOP; i++) phi[i] = (phi[i]+phi[i-1])%MO;39 }40 int main()41 {42 freopen("gcd.in","r",stdin);43 freopen("gcd.out","w",stdout);44 T = read(), init();45 while (T--)46 {47 n = read(), ans = 0, mn = 0x3f3f3f3f;48 for (int i=1; i<=n; i++)49 a[i] = read(), mn = mn>a[i]?a[i]:mn;50 for (int i=1, j=0; i<=mn; i=j+1)51 {52 j = mn, tmp = 1;53 for (int k=1; k<=n; k++) j = std::min(j, a[k]/(a[k]/i));54 for (int k=1; k<=n; k++) tmp = tmp*(a[k]/i)%MO;55 ans = (ans+(phi[j]-phi[i-1]+MO)*tmp%MO)%MO;56 }57 printf("%lld\n",ans);58 }59 return 0;60 }
END