除了最后一題都比較簡單就寫一起了

---

P4450-雙親數

題目鏈接:https://www.luogu.com.cn/problem/P4450

題目大意

給出$A,B,d$求有多少對$(a,b)$滿足$gcd(a,b)=d$且$a\in [1,A],b\in [1,B]$

解題思路

很顯然的容斥，枚舉$d$的倍數$i$，然后容斥系數就是$\mu (\frac{i}{d})$。
時間復雜度$O(n)$

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e6+10; int A,B,d,mu[N],pri[N],cnt; long long ans; bool v[N]; int main() {scanf("%d%d%d",&A,&B,&d);mu[1]=1;for(int i=2;i<N;i++){if(!v[i])pri[++cnt]=i,mu[i]=-1;for(int j=1;j<=cnt&&i*pri[j]<N;j++){v[i*pri[j]]=1;if(i%pri[j]==0)break;mu[i*pri[j]]=-mu[i];}}if(A>B)swap(A,B);for(int i=d;i<=A;i+=d)ans+=1ll*(A/i)*(B/i)*mu[i/d];printf("%lld\n",ans); }

---

P5221-Product

題目鏈接:https://www.luogu.com.cn/problem/P5221

題目大意

給出$n$求
$$\prod _{i=1}^n\prod _{j=1}^n\frac{lcm(i,j)}{gcd(i,j)}$$

解題思路

$\text{CYJian}$的題啊，時限$0.2s?$不過只是看起來花里胡哨，沒有其他$\text{CYJian}$的題那么難。

先簡單把$lcm$拆出來化一下式子
$$\left(\prod _{i=1}^n\prod _{j=1}^{n}i\times j\right)\frac{1}{{\left({\prod }_{i=1}^n{\prod }_{j=1}^{n}gcd(i,j)\right)}^2}$$

左邊那個很容易求就是$(n!{)}^{2n}$，右邊那個因為是乘積所以很好做，直接枚舉質數冪$d^e$，讓有$?\frac{n}{d^e}{?}^2$對數的$gcd$包含$d^e$，會產生這么多的貢獻，但是因為在$d^{e?1}$的時候也統計過一次，所以只需要產生$d$的貢獻就好了。

時間復雜度$O(n\log n)$

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e6+10,P=104857601; ll n,ans,cnt,pri[N]; bool v[N]; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } signed main() {scanf("%lld",&n);ans=1;for(ll i=2;i<=n;i++){if(!v[i]){for(ll j=i;j<=n;j=j*i)ans=ans*power(i,(n/j)*(n/j)%(P-1))%P;pri[++cnt]=i;}for(ll j=1;j<=cnt&&i*pri[j]<=n;j++){v[i*pri[j]]=1;if(i%pri[j]==0)break;}}ans=power(ans*ans%P,P-2);ll f=1;for(ll i=1;i<=n;i++)f=f*i%P;f=power(f,2*n);ans=ans*f%P;printf("%lld",ans);return 0; }

---

P6055-[RC-02]GCD

題目鏈接:https://www.luogu.com.cn/problem/P6055

題目大意

給出$n$求
$$\sum _{i=1}^n\sum _{j=1}^n\sum _{p=1}^{?\frac{n}{j}?}\sum _{q=1}^{?\frac{n}{j}?}[gcd(i,j)=1][gcd(p,q)=1]$$

解題思路

剛開始還以為可以直接暴力整除分塊+杜教篩歐拉函數然后$O(n^{\frac{3}{4}})$搞，然后發現時限是$1s$。

發現這個式子的順序很奇怪，特意的把$j$放在了里面。這個提示我們$j$其實是在枚舉$p$和$q$的$gcd$。
而又$j$和$i$互質，其實這個式子的真正目的是對于每個$i$求有多少對數的$gcd$和$i$互質然后求和。換成式子就是
$$\sum _{i=1}^n\sum _{q=1}^n\sum _{p=1}^n[gcd(gcd(q,p),i)=1]$$
就是三對數之間互質的對數，之間上莫反就可以了
$$\sum _{i=1}^n?\frac{n}{i}{?}^3\mu (i)$$
$n$比較大，要用杜教篩篩一下$mu$

時間復雜度$O(n^{\frac{2}{3}})$？

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<map> #define ll long long using namespace std; const ll N=1e7+10,P=998244353; ll n,cnt,pri[N],mu[N],ans; map<ll,ll> mp; bool v[N]; ll get_sum(ll n){if(mp.find(n)!=mp.end())return mp[n];if(n<N)return mu[n];ll rest=1;for(ll l=2,r;l<=n;l=r+1)r=n/(n/l),(rest+=P-(r-l+1)*get_sum(n/l))%=P;return mp[n]=rest; } signed main() {scanf("%lld",&n);mu[1]=1;for(ll i=2;i<N;i++){if(!v[i])pri[++cnt]=i,mu[i]=-1;for(ll j=1;j<=cnt&&i*pri[j]<N;j++){v[i*pri[j]]=1;if(i%pri[j]==0)break;mu[i*pri[j]]=-mu[i];}}for(ll i=1;i<N;i++)(mu[i]+=mu[i-1])%=P;for(ll l=1,r;l<=n;l=r+1){r=n/(n/l);ll p=n/l;p=p*p%P*p%P;(ans+=p*(get_sum(r)-get_sum(l-1))%P)%=P;}printf("%lld\n",(ans+P)%P);return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的P4450-双亲数,P5221-Product,P6055-[RC-02]GCD【莫比乌斯反演,杜教筛】的全部內容，希望文章能夠幫你解決所遇到的問題。

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