社交网站,网站如何做背景音乐,免费送网站,php 禁止电脑访问网站Easy Math
推式子 ∑i1mμ(in)∑i1mμ(indd)#xff0c;d是n的一个质因子i,d互质项有(−∑i1mμ(ind))#xff0c;由于减去了多余的非互质项#xff0c;所以加上#xff0c;−∑i1mμ(ind)∑i1mdμ(idnd)−∑i1mμ(ind)∑i1mdμ(in)\sum_{i 1} ^{m} \mu(in)\\ \sum_{i 1…Easy Math
推式子
∑i1mμ(in)∑i1mμ(i×nd×d)d是n的一个质因子i,d互质项有(−∑i1mμ(i×nd))由于减去了多余的非互质项所以加上−∑i1mμ(i×nd)∑i1mdμ(i×d×nd)−∑i1mμ(i×nd)∑i1mdμ(i×n)\sum_{i 1} ^{m} \mu(in)\\ \sum_{i 1} ^{m} \mu(i \times \frac{n}{d} \times d)d是n的一个质因子\\ i, d互质项有(-\sum_{i 1} ^{m} \mu(i \times \frac{n}{d}))由于减去了多余的非互质项所以加上\\ -\sum_{i 1} ^{m} \mu(i \times \frac{n}{d}) \sum_{i 1} ^{\frac{m}{d}} \mu(i \times d \times \frac{n}{d})\\ -\sum_{i 1} ^{m} \mu(i \times \frac{n}{d}) \sum_{i 1} ^{\frac{m}{d}} \mu(i \times n)\\ i1∑mμ(in)i1∑mμ(i×dn×d)d是n的一个质因子i,d互质项有(−i1∑mμ(i×dn))由于减去了多余的非互质项所以加上−i1∑mμ(i×dn)i1∑dmμ(i×d×dn)−i1∑mμ(i×dn)i1∑dmμ(i×n)
由此我们可以递归加上杜教筛来得到答案
边界条件n1n 1n1return∑i1mμ(i)return\ \sum_{i 1} ^{m} \mu(i)return ∑i1mμ(i)。
m0,return0m 0, return\ 0m0,return 0。
代码
/*Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include bits/stdc.husing namespace std;typedef long long ll;
const int inf 0x3f3f3f3f;const int N 2e6 10;int prime[N], mu[N], cnt;bool st[N];void init() {mu[1] 1;for(int i 2; i N; i) {if(!st[i]) {prime[cnt] i;mu[i] -1;}for(int j 0; j cnt 1ll * i * prime[j] N; j) {st[i * prime[j]] 1;if(i % prime[j] 0) break;mu[i * prime[j]] -mu[i];}}for(int i 1; i N; i) {mu[i] mu[i - 1];}
}mapll, ll ans_s;ll S(ll n) {if(n N) return mu[n];if(ans_s.count(n)) return ans_s[n];ll ans 1;for(ll l 2, r; l n; l r 1) {r n / (n / l);ans - (r - l 1) * S(n / l);}return ans_s[n] ans;
}ll F(ll n, ll m) {if(n 1) return S(m);if(m 0) return 0;for(int i 0; 1ll * prime[i] * prime[i] n; i) {if(n % prime[i] 0) {return F(n, m / prime[i]) - F(n / prime[i], m);} }return F(n, m / n) - F(n / n, m);
}int main() {
// freopen(in.txt, r, stdin);
// freopen(out.txt, w, stdout);
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);init();ll n, m;scanf(%lld %lld, m, n);ll temp n; for(int i 0; i cnt; i) {int cnt 0;while(n % prime[i] 0) {n / prime[i];cnt;}if(cnt 2) {puts(0);return 0;}}printf(%lld\n, F(temp, m));return 0;
}
