怎么做网站搜索关键词,如何建立手机论坛,中国企业500强,大型门户网站建设步骤P6271 [湖北省队互测2014]一个人的数论 ∑i1nim[gcd(i,n)1]∑d∣nμ(d)dm∑i1ndim由伯努利数可知∑i0nim1m1∑i0mCm1iBi(n1)m−i1设fi1m1Bm−i1Cm1i,则有∑d∣nμ(d)dm(∑i1m1fi(nd)i(nd)m)∑i1m1fini∑d∣nμ(d)dm−i(nm∑d∣nμ(d))考虑后项∑d∣nμ(d)dm−i#xff0c;迪…P6271 [湖北省队互测2014]一个人的数论
∑i1nim[gcd(i,n)1]∑d∣nμ(d)dm∑i1ndim由伯努利数可知∑i0nim1m1∑i0mCm1iBi(n1)m−i1设fi1m1Bm−i1Cm1i,则有∑d∣nμ(d)dm(∑i1m1fi(nd)i(nd)m)∑i1m1fini∑d∣nμ(d)dm−i(nm∑d∣nμ(d))考虑后项∑d∣nμ(d)dm−i迪利克雷卷积乘积为积性函数F(n)∑d∣nμ(d)dm−i,F(1)1,F(pk)1−pm−i\sum_{i 1} ^{n} i ^ m [\gcd(i, n) 1]\\ \sum_{d \mid n} \mu(d) d ^ m \sum_{i 1} ^{\frac{n}{d}} i ^ m\\ 由伯努利数可知\sum_{i 0} ^{n} i ^ m \frac{1}{m 1} \sum_{i 0} ^{m} C_{m 1} ^{i} B_i (n 1) ^{m - i 1}\\ 设f_i \frac{1}{m 1}B_{m - i 1} C_{m 1} ^{i},则有\\ \sum_{d \mid n} \mu(d) d ^ m \left( \sum_{i 1} ^{m 1} f_i (\frac{n}{d}) ^ i (\frac{n}{d}) ^ {m} \right) \\ \sum_{i 1} ^{m 1} f_i n ^ i \sum_{d \mid n} \mu(d) d ^{m - i} (n ^ m \sum_{d \mid n} \mu(d))\\ 考虑后项\sum_{d \mid n} \mu(d) d ^{m - i}迪利克雷卷积乘积为积性函数\\ F(n) \sum_{d \mid n} \mu(d) d ^{m - i}, F(1) 1, F(p ^ k) 1 - p ^{m - i}\\ i1∑nim[gcd(i,n)1]d∣n∑μ(d)dmi1∑dnim由伯努利数可知i0∑nimm11i0∑mCm1iBi(n1)m−i1设fim11Bm−i1Cm1i,则有d∣n∑μ(d)dm(i1∑m1fi(dn)i(dn)m)i1∑m1finid∣n∑μ(d)dm−i(nmd∣n∑μ(d))考虑后项d∣n∑μ(d)dm−i迪利克雷卷积乘积为积性函数F(n)d∣n∑μ(d)dm−i,F(1)1,F(pk)1−pm−i
由于mmm较小且模数是109710 ^ 9 71097所以可以考虑O(m2)O(m ^2)O(m2)递推得到伯努利数之后可以枚举iii然后每次O(w)O(w)O(w)做一次线性筛整体复杂度O(mw)O(m w)O(mw)。
#include bits/stdc.husing namespace std;const int N 1e3 10, mod 1e9 7;int C[N][N], B[N], inv[N], f[N], p[N], n, m;void init() {for (int i 0; i N; i) {C[i][0] C[i][i] 1;for (int j 1; j i; j) {C[i][j] (C[i - 1][j] C[i - 1][j - 1]) % mod;}}inv[1] 1;for (int i 2; i N; i) {inv[i] 1ll * (mod - mod / i) * inv[mod % i] % mod;}B[0] 1;for (int i 1; i N; i) {int cur 0;for (int j 0; j i; j) {cur (cur 1ll * C[i 1][j] * B[j] % mod) % mod;}cur 1ll * cur * inv[i 1] % mod;B[i] (mod - cur) % mod;}
}int quick_pow(int a, int n) {int ans 1;while (n) {if (n 1) {ans 1ll * ans * a % mod;}a 1ll * a * a % mod;n 1;}return ans;
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);init();scanf(%d %d, m, n);for (int i 1; i m 1; i) {f[i] 1ll * inv[m 1] * B[m - i 1] % mod * C[m 1][i] % mod;}int base 1;for (int i 1, w; i n; i) {scanf(%d %d, p[i], w);base 1ll * base * quick_pow(p[i], w) % mod;}int ans 0, now 1;for (int i 1; i m 1; i) {now 1ll * now * base % mod;int cur 1ll * f[i] * now % mod, res 1, po m - i;if (po 0) {po mod - 1;}for (int j 1; j n; j) {res 1ll * res * (1 - quick_pow(p[j], po) mod) % mod;}cur 1ll * cur * res % mod;ans (ans cur) % mod;}printf(%d\n, ans);return 0;
}
