Absolute Math

$$\begin{gathered} 定義c(n)=theprimenhave，c(1)=0,c(2)=1,c(4)=1,c(6)=2 \\ f(n)=\sum _{d\mid n}\mu (d{)}^2=2^{c(n)} \\ f(ab)=\frac{f(a)\times f(b)}{f(gcd(a,b))} \\ \sum _{i=1}^m\frac{f(n)\times f(i)}{f(gcd(n,i))} \\ f(n)\sum _{d\mid n}\frac{1}{f(d)}\sum _{i=1}^{\frac{m}{d}}f(id)[gcd(i,\frac{n}{d})=1] \\ f(n)\sum _{d\mid n}\frac{1}{f(d)}\sum _{k\mid \frac{n}{d}}\mu (k)\sum _{i=1}^{\frac{m}{kd}}f(ikd) \\ T=kd \\ f(n)\sum _{T\mid n}\sum _{i=1}^{\frac{m}{T}}f(iT)\sum _{d\mid T}\frac{\mu (\frac{T}{d})}{f(d)} \\ F(m,n)=\sum _{i=1}^{m}f(in),g(n)=\sum _{d\mid n}\frac{\mu (\frac{n}{d})}{f(d)} \\ F(m,n)=f(n)\sum _{T\mid n}F(\frac{m}{T},T)g(T) \\ g=\mu ?\frac{1}{f}，是一個積性函數 \\ g(1)=1 \\ g(p)=\frac{\mu (p)}{f(1)}+\frac{\mu (1)}{f(p)}=?1+\frac{1}{2}=?\frac{1}{2} \\ g(p^x)[x>=2]=\frac{\mu (1)}{f(p^x)}+\frac{\mu (p)}{f(p^{x?1})}=\frac{1}{2}?\frac{1}{2}=0 \\ 然后遞歸求解，卡卡常 \end{gathered}$$

/*Author : lifehappy */ #include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1e7 + 10, mod = 1e9 + 7, inv2 = mod + 1 >> 1;int prime[N], sum[N], g[N], f[N], cnt;bool st[N];void init() {f[1] = g[1] = 1;for(int i = 2; i < N; i++) {if(!st[i]) {prime[++cnt] = i;f[i] = 2;g[i] = mod - inv2;}for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {st[i * prime[j]] = 1;if(i % prime[j] == 0) {f[i * prime[j]] = f[i];break;}f[i * prime[j]] = f[i] * 2;g[i * prime[j]] = 1ll * g[i] * g[prime[j]] % mod;}}for(int i = 1; i < N; i++) {sum[i] = (f[i] + sum[i - 1]) % mod;} }ll solve(int m, int n) {if(m == 0) return 0;if(m == 1) return f[n];if(n == 1) return sum[m];ll ans = 0;//發現m <= 20的時候是最優的……if(m <= 20 && 1ll * n * m < N) {for(int i=1;i<=m;i++)ans = (ans + f[i * n]) % mod;return ans;}for(int i = 1; 1ll * i * i <= n; i++) {if(n % i == 0){if(g[i]){ans = (ans + solve(m / i, i) * g[i] % mod) % mod;}if(i * i !=n && g[n / i]){ans = (ans + solve(m / (n / i), n / i)*g[n / i]) % mod;}}}return ans * f[n] % mod; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);init();int T;scanf("%d", &T);while(T--) {int n, m;scanf("%d %d", &n, &m);printf("%lld\n", solve(m, n));}return 0; } /*杭電的測評機比自己的老年機跑的還慢…… */

總結

以上是生活随笔為你收集整理的Absolute Math (HDU 6868)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。