F.Frog
题意
n个青蛙m个石子 下标从0到m-1
每只青蛙一次条ai格 假如它在x处下次它会在 (ai+x)%m 处
让这n只青蛙一直跳 求被青蛙跳到的石子下标和 被跳过多次只计算1次
题解
不难发现 对于某只青蛙而言它能跳到的石头一定是gcd(a[i],m)的倍数
而对于某块石头x而言若存在gcd(a[i],m)是x的因子 即 gcd(a[i],m)|m 那它就会被跳到
那我们对于gcd(a[i],m)=g，它产生的贡献是：
g ×(首项+末项)× (项数)/2=g×(1+m/g-1)×(m/g-1)/2=m×(m/g-1)/2
那么问题来了，被重复计算的怎么减掉呢？
由于gcd(a[i],m)一定是m的因子集合的子集 我们可以用它的因子来计算贡献
先求出m的所有因子x,存入phi中,再判断这些因子x中哪些是gcd(a[i],m)的倍数
cnt[x]=1 表示第x个因子是gcd(a[i],m)的倍数 要被计算到贡献中1次
最后在遍历所有因子 求它们对ans的贡献
对于第x个因子它产生的贡献是 ：m × (m/phi[x]-1)/2 ×(cnt[x]-repeat[x])
repeat[x]表示是第x个因子倍数的石子已经被重复计算过的次数 要从贡献中减去
每次求完这个因子x的贡献后 for循环找出比它大的因子y中有哪些是因子x的倍数
并更新 repeat[y]+=（cnt[x]-repeat[x]) 表示因子y的贡献被它更小的因子x已经多计算了
(cnt[x]-repeat[x]) 次 这部分就是容斥原理的体现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
typedef pair<ll,ll> P;
const int mod=2e3;
const int Max=1e5+5;
int gcd[Max],cnt[Max],repeat[Max];
int main(){
Turnoff;
int t,ti=1;cin>>t;
while(t--){
vector<ll>phi;
memset(cnt,0,sizeof cnt);
memset(repeat,0,sizeof repeat);
ll n,m;cin>>n>>m;
for(int i=0;i<n;i++){
ll temp;cin>>temp;
gcd[i]=__gcd(temp,m);
}
phi.push_back(1);
for(int i=2;i*i<=m;i++){
if(m%i)continue;
phi.push_back(i);
if(i*i!=m)phi.push_back(m/i);
}
sort(phi.begin(),phi.end());
for(int i=0;i<n;i++){
for(int j=0;j<phi.size();j++){
if(phi[j]%gcd[i])continue;
cnt[j]=1;
}
}
ll ans=0;
for(int i=0;i<phi.size();i++){
if(!cnt[i])continue;
ans+=m*(m/phi[i]-1)/2*(cnt[i]-repeat[i]);
for(int j=i+1;j<phi.size();j++){
if(phi[j]%phi[i])continue;
repeat[j]+=(cnt[i]-repeat[i]);
}
}
cout<<"Case #"<<ti++<<": "<<ans<<endl;
}
}
|
为什么不能直接通过枚举gcd(a[i],m)容斥直接计算贡献 就是用gcd(a[i],m)组成的集合来计算ans呢
不加入求m的因子集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
typedef pair<ll,ll> P;
const int mod=2e3;
const int Max=1e5+5;
int gcd[Max],cnt[Max],repeat[Max];
int main(){
Turnoff;
int t,ti=1;cin>>t;
while(t--){
vector<ll>phi;
memset(repeat,0,sizeof repeat);
ll n,m;cin>>n>>m;
for(int i=0;i<n;i++){
ll temp;cin>>temp;
gcd[i]=__gcd(temp,m);
cnt[i]=1;
}
sort(gcd,gcd+n);
ll ans=0;
for(int i=0;i<n;i++){
ans+=m*(m/gcd[i]-1)/2*(cnt[i]-repeat[i]);
for(int j=i+1;j<n;j++){
if(gcd[j]%gcd[i])continue;
repeat[j]+=(cnt[i]-repeat[i]);
}
}
cout<<"Case #"<<ti++<<": "<<ans<<endl;
}
}
|
此外还有一种分析
因为gcd(x,m)|m 所以枚举m的因子 假如对于m的一个因数k，如果存在一个i使得k能被ai整除(能被跳到)，则此时对于所有石头x符合gcd(x,m)==k的都对答案产生贡献：
∑x,{gcd(x,m)=k} = k*∑x/k,{gcd(x/k,m/k)=1}
而
∑x/k,{gcd(x/k,m/k)=1} = φ(m/k)*(m/k)/2
这里用到一个结论小于n于n互质的数的和 sum=φ(n)*n/2
推倒 假设一个数xi与n互质 那么 n-xi也与n互质 (更相减损法求gcd)
所以 sum=(x1 +n-x1)+(x2+n-x2)+…..(xφ(n)+n-xφ(n))/2
除2是因为每个与n互质的数都被枚举了2次即(n-xi)=xj
参考博客