Codeforces Edu 81 D(数学) & E(数据结构)
这场打的贼烂，D和E都挺可做的，居然没时间写。搞了半天签了三道，B一个小bug被hack，CTLE在test 30 。
D. Same GCDs
分析 ： 给出 a 和 m ，问有多少个 x 使得 GCD(a , m) = GCD(a + x , m) 。
我的做法: 简单容斥，详见代码 。 这题其实挺简单的，没写出来不应该
code :
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> p;
ll GCD(ll a,ll b){return b==0?a:GCD(b,a%b);}
ll rongchi(ll x)
{
ll ans=0;
for(int i=1;i<(1<<p.size());i++) {
int bits=0; ll mul=1;
for(int j=0;j<p.size();j++)
if(i&(1<<j)) mul*=p[j],bits++;
if(bits&1) ans+=x/mul;
else ans-=x/mul;
}
return ans;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
p.clear();
ll a,m,gcd;
scanf("%lld%lld",&a,&m);
gcd=GCD(a,m);
if(gcd==1) printf("%lld\n",phi(m));
else {
m/=gcd; a/=gcd;
ll tmp=m;
for(ll i=2;i*i<=tmp;i++)
if(tmp%i==0) {
p.push_back(i);
while(tmp%i==0) tmp/=i;
}
if(tmp>1) p.push_back(tmp);
printf("%lld\n",m-(rongchi(a+m-1)-rongchi(a)));
}
}
return 0;
} tutorial的做法，虽然他写了一堆我没看明白，不过直接看代码倒是一下就懂了
code :
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll GCD(ll a,ll b){return b==0?a:GCD(b,a%b);}
ll phi(ll n)
{
ll ans=n;
for(ll i=2;i*i<=n;i++)
if(n%i==0) {
ans=ans/i*(i-1);
while(n%i==0) n/=i;
}
if(n>1) ans=ans/n*(n-1);
return ans;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ll a,m;
scanf("%lld%lld",&a,&m);
printf("%lld\n",phi(m/GCD(a,m)));
}
return 0;
} E. Permutation Separation
分析 ：
