HDU5514 Frogs

---

題意：將\([0,m)\)所有符合\(a[i]*t ~mod~ m\)的值求和

做法：

\(a[i]*t ~mod~ m\) 會在 \(gcd(a[i],m)\) 的倍數出現，因此問題等價與求：
\[ \sum_{i=1}^{m-1} [ [(a[1],m)|i] or [(a[2],m)|i] or ... or [(a[n],m)|i] ] i \]

對于一個x，使得\(gcd(x,m)=g\)，當存在一個\(gcd(a[i],m)|g\)時，則這個x就會被計入答案。
那么就可以枚舉\(g\)來計算貢獻了
\(gcd(i,m)=g\), 則\(gcd(i/g,m/g)=1\)，那么對于一個\(g\)如果他存在一個\(gcd(a[i],m)|g\)，貢獻就是：
\[ \sum_{i=1}^{m-1} [gcd(i/g,m/g)=1]i = \sum_{i=1}^{m/g} [gcd(i,m/g)=1]i*g \]
又因為
\[ \sum_{i=1}^{n}[gcd(i,n)=1]i = \frac{\varphi(n)*n}{2} \]
證明：
\[ \sum_{i=1}^{n}[gcd(i,n)=1]i + \sum_{i=1}^{n}[gcd(n-i,n)=1](n-i) \\ = \sum_{i=1}^n [gcd(i,n)=1]n = n\varphi(n)\\ \sum_{i=1}^{n}[gcd(i,n)=1]i = \frac{\varphi(n)*n}{2} \]

枚舉m的約數g計算即可

#include <bits/stdc++.h> typedef long long ll; const int N = 1e4 + 7; using namespace std; int T,n; ll m,a[N];// //gcd(x,m) = g => gcd(x/g,m/g) = 1 // //FOR : g|m // if FOR : gcd(a[i],m)|g // ans += {\sum [gcd(i/g,m/g) == 1]*i => \phi(m/g)*(m/g)/2*g => \phi(m/g)*m/2} // //hints: //[gcd(i,n)==1] = [gcd(i,n-i)==1] //\sum [gcd(i,n)==1]*i + \sum [gcd(n-i,n)==1]*(n-i) = n*\sum [gcd(i,n)==1] = n*phi(n) //=> \sum [gcd(i,n)==1]*i = n*phi(n)/2ll b[1000007]; int cnt = 0; int ck(ll g) {for(int i=0;i<n;++i) if(g%a[i]==0) return 1;return 0; } ll phi(ll x) {ll t = x;for(int i=2;i*i<=x;++i) if(x%i==0) {t-=t/i;while(x%i==0) x/=i;}if(x>1)t-=t/x;return t; } int main() {scanf("%d",&T);for(int ti=1;ti<=T;++ti) {scanf("%d%lld",&n,&m);int f = 0;for(int i=0;i<n;++i) {scanf("%lld",&a[i]);a[i] = __gcd(a[i],m);if(a[i]==1) f=1;}if(f) {printf("Case #%d: %lld\n",ti,(m-1)*m>>1LL);continue;}sort(a,a+n);n = unique(a,a+n) - a;cnt = 0;for(ll i=1;i*i<=m;++i) {if(m%i==0) {if(i*i == m) b[cnt++] = i;else {b[cnt++] = i;if(m/i!=1) b[cnt++] = m/i;}}}sort(b,b+cnt);cnt = unique(b,b+cnt) - b;ll ans = 0;for(int i=0;i<cnt;++i) {if(b[i]<m&&ck(b[i])) {ans+= phi(m/b[i]);}}ans*=m; ans/=2;printf("Case #%d: %lld\n",ti,ans);}return 0; }

轉載于:https://www.cnblogs.com/RRRR-wys/p/9689624.html

總結

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

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