大意:
![](https://www.nowcoder.com/equation?tex=%E6%9C%89m%E4%B8%AA%E7%9F%B3%E5%A4%B4%EF%BC%8C%E6%A0%87%E5%8F%B7%E4%BB%8E0%5Csim%20m-1%EF%BC%8C%E6%9C%89n%E5%8F%AA%E9%9D%92%E8%9B%99%EF%BC%8C%E6%89%80%E6%9C%89%E9%9D%92%E8%9B%99%E4%B8%80%E5%BC%80%E5%A7%8B%E9%83%BD%E5%9C%A8%E7%BC%96%E5%8F%B7%E4%B8%BA0%E7%9A%84%E7%9F%B3%E5%A4%B4%E4%B8%8A&preview=true)
![](https://www.nowcoder.com/equation?tex=%E6%AF%8F%E5%8F%AA%E9%9D%92%E8%9B%99%E6%AF%8F%E6%AC%A1%E5%8F%AF%E4%BB%A5%E8%B7%B3%E7%9A%84%E8%B7%9D%E7%A6%BB%E4%B8%BAa%5Bi%5D%EF%BC%8C%E6%B1%82%E6%89%80%E6%9C%89%E9%9D%92%E8%9B%99%E8%83%BD%E5%A4%9F%E5%8D%A0%E9%A2%86%E7%9A%84%E7%9F%B3%E5%A4%B4%E7%9A%84%E7%BC%96%E5%8F%B7%E4%B9%8B%E5%92%8C&preview=true)
![](https://www.nowcoder.com/equation?tex=%E6%80%9D%E8%B7%AF%EF%BC%9A&preview=true)
![](https://www.nowcoder.com/equation?tex=%E6%AF%8F%E4%B8%AA%E9%9D%92%E8%9B%99%E5%8F%AF%E4%BB%A5%E8%B7%B3%E7%9A%84%E4%BD%8D%E7%BD%AE%E5%BA%94%E8%AF%A5%E6%98%AFgcd(a%5Bi%5D%EF%BC%8Cm)%E7%9A%84%E5%80%8D%E6%95%B0&preview=true)
![](https://www.nowcoder.com/equation?tex=%E5%A6%82%E6%9E%9Cgcd(a%5Bi%5D%2Cm)%7Cx%2C%E7%9F%B3%E5%AD%90x%E4%BC%9A%E8%A2%AB%E7%AC%ACi%E4%B8%AA%E9%9D%92%E8%9B%99%E8%B8%A9%E5%88%B0&preview=true)
![](https://www.nowcoder.com/equation?tex=gcd(a%5Bi%5D%2Cm)%7Cx%E8%A1%A8%E7%A4%BA%E5%90%8E%E8%80%85%E6%98%AF%E5%89%8D%E8%80%85%E7%9A%84%E5%80%8D%E6%95%B0&preview=true)
![](https://www.nowcoder.com/equation?tex=sum(q)%3D%5Cfrac%7B%5Cphi%20(q)*q%7D%7B2%7D&preview=true)
![](https://www.nowcoder.com/equation?tex=sim(q)%E6%98%AF1%5Csim%20q-1%E4%B8%8Eq%E4%BA%92%E8%B4%A8%E7%9A%84%E6%95%B0%E7%9A%84%E5%92%8C%EF%BC%8C%5Cphi%20(q)%E6%98%AF1%5Csim%20q-1%E4%B8%8Eq%E4%BA%92%E8%B4%A8%E7%9A%84%E6%95%B0%E7%9A%84%E4%B8%AA%E6%95%B0&preview=true)
![](https://www.nowcoder.com/equation?tex=%E5%8F%AF%E4%BB%A5%E7%89%B9%E5%88%A4gcd(a%5Bi%5D%2Cm)%3D%3D1%EF%BC%8C%E8%BF%99%E6%97%B6%E7%AD%94%E6%A1%88%E5%B0%B1%E6%98%AF%5Cfrac%7Bm*(m-1)%7D%7B2%7D&preview=true)
欧拉函数求和+思维
![](https://www.nowcoder.com/equation?tex=%E5%BD%93m%3D20%EF%BC%8Ca%5B%5D%3D2%2C5&preview=true)
![](https://www.nowcoder.com/equation?tex=%E5%A6%82%E6%9E%9C%E6%9E%9A%E4%B8%BEa%5Bi%5D%E7%9A%84%E8%B4%A1%E7%8C%AE%E6%B1%82%E5%92%8C%EF%BC%8C%E4%BC%9A%E5%87%BA%E7%8E%B0%E9%87%8D%E5%A4%8D%E8%AE%A1%E7%AE%97&preview=true)
![](https://www.nowcoder.com/equation?tex=%E5%8F%AF%E4%BB%A5%E8%80%83%E8%99%91%E6%9E%9A%E4%B8%BEm%E7%9A%84%E6%AF%8F%E4%B8%AA%E5%9B%A0%E5%AD%90%E7%9A%84%E8%B4%A1%E7%8C%AE%EF%BC%88%E8%BF%99%E4%B8%AA%E5%8E%9F%E7%90%86%E6%88%91%E6%B2%A1%E6%90%9E%E6%B8%85%E6%A5%9A%EF%BC%8C%E7%BD%91%E4%B8%8A%E4%B9%9F%E6%B2%A1%E7%9C%8B%E5%88%B0%E6%9C%89%E4%BA%BA%E8%A7%A3%E9%87%8A%EF%BC%89&preview=true)
![](https://www.nowcoder.com/equation?tex=m%E7%9A%84%E5%9B%A0%E5%AD%90%E6%9C%892%E3%80%814%E3%80%815%E3%80%8110&preview=true)
![](https://www.nowcoder.com/equation?tex=%E7%9F%B3%E5%AD%90x%3D2%E9%9D%92%E8%9B%99%E5%8F%AF%E4%BB%A5%E8%B8%A9%E5%88%B0%EF%BC%8C%E8%B4%A1%E7%8C%AE%E6%98%AF2*(1%2B3%2B7%2B9)&preview=true)
![](https://www.nowcoder.com/equation?tex=%E5%8D%B32*%5Cfrac%7B%5Cphi%20(%5Cfrac%7B20%7D%7B2%7D)*%5Cfrac%7B20%7D%7B2%7D%7D%7B2%7D&preview=true)
![](https://www.nowcoder.com/equation?tex=1%5Csim%209%E4%B8%8E10%E4%BA%92%E8%B4%A8%E7%9A%84%E6%95%B0%E6%98%AF1%E3%80%813%E3%80%817%E3%80%819%EF%BC%8C%E8%BF%99%E6%A0%B7%E5%BE%97%E5%88%B0%E7%9A%84%E6%95%B0%E4%B8%8E2%E7%9A%84%E4%B9%98%E7%A7%AF%E4%B8%8D%E4%BC%9A%E5%A4%A7%E4%BA%8E%E7%AD%89%E4%BA%8Em%EF%BC%8C%E5%90%8C%E6%97%B6%E4%B9%9F%E4%B8%8D%E4%BC%9A%E5%92%8C%E5%85%B6%E5%AE%83%E5%9B%A0%E5%AD%90%E5%BE%97%E5%88%B0%E7%9A%84%E5%80%BC%E9%87%8D%E5%A4%8D&preview=true)
![](https://www.nowcoder.com/equation?tex=%E7%9F%B3%E5%AD%90x%3D4%E9%9D%92%E8%9B%99%E5%8F%AF%E4%BB%A5%E8%B8%A9%E5%88%B0%EF%BC%8C%E8%B4%A1%E7%8C%AE%E6%98%AF4*(1%2B2%2B3%2B4)&preview=true)
![](https://www.nowcoder.com/equation?tex=%E5%8D%B34*%5Cfrac%7B%5Cphi%20(%5Cfrac%7B20%7D%7B4%7D)*%5Cfrac%7B20%7D%7B4%7D%7D%7B2%7D&preview=true)
![](https://www.nowcoder.com/equation?tex=x%3D5%E3%80%8110%E5%90%8C%E4%B8%8A&preview=true)
![](https://www.nowcoder.com/equation?tex=%E5%8D%B3%EF%BC%8C%E5%A6%82%E6%9E%9Cx%E8%83%BD%E8%A2%AB%E8%B8%A9%E5%88%B0%EF%BC%8C%E8%B4%A1%E7%8C%AE%E5%B0%B1%E6%98%AF%5Cfrac%7B%5Cphi%20(%5Cfrac%7Bm%7D%7Bx%7D)*m%7D%7B2%7D&preview=true)
![](https://www.nowcoder.com/equation?tex=%E5%8F%AF%E4%BB%A5%E5%8F%91%E7%8E%B0%E8%BF%99%E6%A0%B7%E7%BB%9F%E8%AE%A1%E5%BE%88%E5%B7%A7%E5%A6%99%EF%BC%8C%E4%B8%8D%E4%BC%9A%E6%9C%89%E9%87%8D&preview=true)
![](https://www.nowcoder.com/equation?tex=%E5%A4%8D%E6%9D%82%E5%BA%A6O(%5Csqrt%7Bm%7D*%5Csqrt%5B4%5D%7Bm%7D)&preview=true)
![](https://www.nowcoder.com/equation?tex=My%20Code%3A&preview=true)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4+10;
ll com[maxn];
ll t,n,m,ans;
ll euler(ll x) {
ll ans = x;
for (ll i = 2; i * i <= x; ++i) {
if (x % i == 0) {
ans = ans / i * (i - 1);
while (x % i == 0) x /= i;
}
}
if (x != 1) ans = ans / x * (x - 1);
return ans;
}
bool check(ll x) {
for(int i = 0; i < n; i++)
if(x%com[i] == 0)
return true;
return false;
}
int main() {
cin>>t;
for(ll cas=1;cas<=t;++cas,ans=0) {
bool Prime = false;
cin>>n>>m;
for(ll i=0,x,g;i<n;++i) {
cin>>x;
com[i]=__gcd(x,m);
if(com[i] == 1) Prime = true;
}
if(Prime) ans = m*(m-1)/2;
else {
for(int i = 2; i*i <= m; i++) if(m%i == 0){
if(check(i)) ans += euler(m/i)*m/2;
if(i*i!=m && check(m/i)) ans+= euler(i)*m/2;
}
}
printf("Case #%lld: %lld\n",cas,ans);
}
}
容斥原理
![](https://www.nowcoder.com/equation?tex=%E5%A6%82%E6%9E%9C%E4%B8%8D%E8%80%83%E8%99%91%E9%87%8D%E5%A4%8D%E8%AE%A1%E7%AE%97%EF%BC%8C%E6%AD%A5%E9%95%BFstep%E7%9A%84%E8%B4%A1%E7%8C%AE%E4%B8%BAm*%5Cfrac%7B%5Cfrac%7Bm%7D%7Bstep%7D-1%7D%7B2%7D&preview=true)
![](https://www.nowcoder.com/equation?tex=%E8%80%83%E8%99%91%E5%88%B0%E4%BC%9A%E9%87%8D%E5%A4%8D%E8%AE%A1%E7%AE%97%EF%BC%8C%E5%A6%82%E6%9E%9Cm%E7%9A%84%E5%9B%A0%E5%AD%90x%E9%9D%92%E8%9B%99%E8%83%BD%E8%B8%A9%E5%88%B0%EF%BC%8C%E5%9C%A8%E8%AE%A1%E7%AE%97%E5%89%8D%E7%94%A8cnt%5Bx%5D%3D1%E6%A0%87%E8%AE%B0x%E5%BA%94%E8%AF%A5%E8%A2%AB%E7%AE%97%E4%B8%80%E6%AC%A1&preview=true)
![](https://www.nowcoder.com/equation?tex=%E8%AE%A1%E7%AE%97%E6%97%B6%E4%BB%8E%E5%B0%8F%E5%88%B0%E5%A4%A7%E9%81%8D%E5%8E%86m%E7%9A%84%E5%9B%A0%E5%AD%90%EF%BC%8Ctmp%3Dcnt%5Bi%5D-sum%5Bi%5D%E8%A1%A8%E7%A4%BAi%E5%8F%8Ai%E7%9A%84%E5%80%8D%E6%95%B0%E5%AF%B9%E7%AD%94%E6%A1%88%E7%9A%84%E8%B4%A1%E7%8C%AE%E6%83%85%E5%86%B5&preview=true)
![](https://www.nowcoder.com/equation?tex=%E5%A6%82%E6%9E%9Ctmp%3C0%E8%A1%A8%E7%A4%BAi%E5%8F%8Ai%E7%9A%84%E5%80%8D%E6%95%B0%E8%A2%AB%E5%A4%9A%E5%8A%A0%E4%BA%86tmp%E6%AC%A1%EF%BC%8Ctmp%3D1%E8%A1%A8%E7%A4%BAi%E5%8F%8Ai%E7%9A%84%E5%80%8D%E6%95%B0%E8%BF%98%E6%B2%A1%E8%A2%AB%E8%AE%A1%E7%AE%97%2Ctmp%3D0%E8%A1%A8%E7%A4%BAi%E5%8F%8Ai%E7%9A%84%E5%80%8D%E6%95%B0%E5%B7%B2%E7%BB%8F%E8%AE%A1%E7%AE%97%E6%88%96%E8%80%85%E6%B2%A1%E6%9C%89%E8%B4%A1%E7%8C%AE&preview=true)
![](https://www.nowcoder.com/equation?tex=1%E6%95%85m%E7%9A%84%E5%9B%A0%E5%AD%90i%E7%9A%84%E8%B4%A1%E7%8C%AE%E4%B8%BAm*%5Cfrac%7B%5Cfrac%7Bm%7D%7Bstep%7D-1%7D%7B2%7D*(cnt%5Bi%5D-sum%5Bi%5D)&preview=true)
![](https://www.nowcoder.com/equation?tex=%E5%8A%A0%E4%B8%80%E6%AC%A1x%EF%BC%8Csum%5Bk%5D%E5%B0%B1%E5%8A%A0%E4%B8%80%E6%AC%A1%EF%BC%8C%E5%87%8F%E4%B8%80%E6%AC%A1x%EF%BC%8Csum%5Bk%5D%E5%B0%B1%E5%87%8F%E4%B8%80%E6%AC%A1%EF%BC%8C%E8%A1%A8%E7%A4%BAx%E5%AE%9E%E9%99%85%E8%A2%AB%E5%8A%A0%E4%BA%86%E5%87%A0%E6%AC%A1%EF%BC%8Ck%E4%B8%BAx%E7%9A%84%E5%80%8D%E6%95%B0&preview=true)
![](https://www.nowcoder.com/equation?tex=%E8%AE%A1%E7%AE%97%E5%AE%8C%E4%B8%80%E4%B8%AA%E5%9B%A0%E5%AD%90i%E5%90%8E%E7%BB%B4%E6%8A%A4i%E7%9A%84%E5%80%8D%E6%95%B0%E7%9A%84sum%5B%5D%E6%95%B0%E7%BB%84%EF%BC%8Csum%5Bk%5D%2B%3Dcnt%5Bi%5D-sum%5Bi%5D&preview=true)
![](https://www.nowcoder.com/equation?tex=%E4%B8%8D%E8%80%83%E8%99%91%E8%BE%93%E5%85%A5%EF%BC%8C%E5%A4%8D%E6%9D%82%E5%BA%A6O((log%20_%7B2%7Dm)%5E%7B2%7D)&preview=true)
![](https://www.nowcoder.com/equation?tex=My%20Code%3A&preview=true)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>v;
const int maxn=1e5+5;
ll cnt[maxn],sum[maxn];
int main(void) {
ll t,n,m;
cin>>t;
for(int cas=1;cas<=t;++cas) {
cin>>n>>m;
memset(cnt,0,sizeof cnt);
memset(sum,0,sizeof sum);
v.clear();
for(int i=2;i*i<m;++i) if(m%i==0) {
v.push_back(i);
v.push_back(m/i);
}
v.push_back(1);
sort(v.begin(),v.end());
for(ll i=1,x,g;i<=n;++i) {
cin>>x;
g=__gcd(x,m);
for(int j=0;j<v.size();++j) if(v[j]%g==0)
cnt[j]=1;
}
ll res=0;
for(int i=0;i<v.size();++i) {
res+=m*(m/v[i]-1)/2*(cnt[i]-sum[i]);
for(int j=i+1;j<v.size();++j) {
if(v[j]%v[i]==0) sum[j]+=cnt[i]-sum[i];
}
}
printf("Case #%lld: %lld\n",cas,res);
}
}