ACM-ICPC 2018 徐州賽區(qū)網(wǎng)絡(luò)預(yù)賽 D. EasyMath

---

做法：
\[f(m,n) = \sum _{i=1}^{m} \mu(in) = \sum_{i=1}^{m}[gcd(i,n)=1]\mu(i)\mu(n) = \mu(n)\sum_{d|n}\mu(d)f(\frac{m}ze8trgl8bvbq,d)\]
邊界: n=1，杜教篩求\(\sum_{i=1}^{m}\mu(i)\)，m = 1, 返回\(\mu(n)\)，預(yù)處理盡可能把空間卡滿(mǎn)。

2個(gè)小時(shí)的時(shí)候就推出來(lái)了這個(gè)式子，不會(huì)算復(fù)雜度，本校沒(méi)人過(guò)。。。于是成功放棄了。。。

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define per(i,a,b) for(int i=a;i>=b;--i) #define pb push_back #define mp make_pair #define PII pair<int,int> #define sc second typedef long long ll; const int N = 1e7 + 13000000 + 1; const int LM = 13000000; using namespace std; ll n,m; bool notp[N]; int p[N], smiu[N]; short miu[N]; void init() {notp[1] = 1;miu[1] = 1;for(int i=2;i<=1e7+LM;++i) {if(!notp[i]) p[++p[0]] = i, miu[i] = -1;for(int j=1;j<=p[0]&&p[j]*i<=1e7+LM;++j) {notp[i*p[j]] = 1;if(i%p[j] == 0) {miu[i*p[j]] = 0;break;}miu[i*p[j]] = miu[i]*miu[p[j]];}}for(int i=1;i<=1e7+LM;++i) smiu[i] = smiu[i-1] + miu[i]; } ll g(ll n) {if(n<=1e7+LM) return smiu[n];if(n == 1) return 1;ll ans = 1;for(ll i=2,r;i<=n;i=r+1) {r = (n/(n/i));ans -= (r-i+1LL)*g(n/i);}return ans; } void chai(ll x,vector<ll> &v,ll &mu) {v.clear();mu = 1;for(int i=1;i<=p[0]&&1LL*p[i]*p[i]<=x;++i) {if(x%p[i]==0) {int cnt = 0;v.pb(p[i]);mu = -mu;while(x%p[i]==0) x/=p[i], cnt++;if(cnt>1) mu = 0;}}if(x!=1) mu=-mu, v.pb(x); } ll f(ll m,ll n) {if(m == 0 || n == 0) return 0;ll mu_n, ans = 0;if(m == 1 && n <= 1e7+LM) return miu[n];vector<ll> v;chai(n,v,mu_n);if(m == 1) return mu_n;if(n == 1) return g(m);if(mu_n == 0) return 0;int cnt = v.size();for(int s=0;s<(1<<cnt);++s) {ll d = 1, mu_d = 1;for(int i=0;i<cnt;++i) if(s&(1<<i)){d = d*v[i];mu_d = -mu_d;}if(m >= d) ans += mu_d*f(m/d,d);}ans *= mu_n;return ans; }int main() {init();scanf("%lld%lld",&m,&n);printf("%lld\n",f(m,n));return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/RRRR-wys/p/9615109.html

總結(jié)

以上是生活随笔為你收集整理的ACM-ICPC 2018 徐州赛区网络预赛 D. EasyMath的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。