网站设计制作一条龙,涟水县住房和城乡建设局网站,网站备案 时间,网站建设公司专业网站开发制作初涉的话先留坑吧 题目大意 $\sum_{i_1}^{a_1}\sum_{i_2}^{a_2}\cdots\sum_{i_m}^{a_m}(i_1,i_2,\cdots,i_m)$ $a_i1e6,2m10$ 题目分析 首先寄存两篇比较好的博客#xff1a; 1.铃悬的数学小讲堂——狄利克雷卷积与莫比乌斯反演 2.[学习笔记]莫比乌斯反演常见模型… 初涉的话先留坑吧 题目大意 $\sum_{i_1}^{a_1}\sum_{i_2}^{a_2}\cdots\sum_{i_m}^{a_m}(i_1,i_2,\cdots,i_m)$ $a_i1e6,2m10$ 题目分析 首先寄存两篇比较好的博客 1.铃悬的数学小讲堂——狄利克雷卷积与莫比乌斯反演 2.[学习笔记]莫比乌斯反演常见模型 这个问题可以推广至一类模型$\sum_{i1}^n\sum_{j1}^mf[\gcd(i,j)]$. 该模型的推论是$原式\sum_{u1}^{\min(n,m)}\lfloor\frac{n}{u}\rfloor\lfloor\frac{m}{u}\rfloor\sum_{d|u}f[d]\mu(\frac{u}{d})$ 注意到在本题中$fid$那么也就是说$原式\sum_{u1}^{\min(n,m)}\lfloor\frac{n}{u}\rfloor\lfloor\frac{m}{u}\rfloor \varphi(u)$. 因此先一遍线性筛求$\varphi$的前缀和再数论分块做$\lfloor\frac{n}{u}\rfloor$这一部分。 本题对模型的转化还不算太深算是比较裸的反演 1 #includebits/stdc.h2 typedef long long ll;3 const int maxn 13;4 const int MO 1e97;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); chgetchar())
19 if (ch-) fl 1;
20 for (; isdigit(ch); chgetchar())
21 num (num1)(num3)ch-48;
22 if (fl) num -num;
23 return num;
24 }
25 void init()
26 {
27 phi[1] 1;
28 for (int i2; iTOP; i)
29 {
30 if (!vis[i]) pr[pr[0]] i, phi[i] i-1;
31 for (int j1; (jpr[0])(pr[j]*iTOP); 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 i2; iTOP; 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 i1; in; i)
49 a[i] read(), mn mna[i]?a[i]:mn;
50 for (int i1, j0; imn; ij1)
51 {
52 j mn, tmp 1;
53 for (int k1; kn; k) j std::min(j, a[k]/(a[k]/i));
54 for (int k1; kn; 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转载于:https://www.cnblogs.com/antiquality/p/9892267.html
