题目链接
点这里
A
就是求gcd(a,m)=gcd(a+x,m)的个数，把区间对称一下之后，就发现求得是phi(b/g);
代码
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
ll p(ll x,int cnt){
if(cnt<0)return 0;
if(cnt==0)return 1;
for(int i=2;i<=cnt;i++){
x*=x;
}
return x;
}
ll getphi(ll x){
ll ans = x;
for(int i=2;1ll*i*i<=x;i++){
if(x%i==0){
ans-=ans/i;
while(x%i==0)x/=i;
}
}
if(x!=1)ans-=ans/x;
return ans;
}
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
ll a,b;
scanf("%lld %lld",&a,&b);
ll g = gcd(a,b);
b/=g;
printf("%lld\n",getphi(b));
}
}
|
C
题意
就是求用<=m的数填满足n*n矩阵每行每列上有1的个数
思路
用容斥原理的话就可以得到
答案=总方案-一行不满足-一列不满足+(二行不满足+二列部不满足+一行一列不满足)
这个表示了选择的方法，然后再看看选择方块后的方案书，当选了i行j列后，得到的格子数为$ni+nj-ij$然后这些格子是不满足的，也就是最小值>1，所以能填的为$(m-1)^{ni+nj-ij}$然后剩下的那些满足的也就是$nn-ni+nj-ij$,能填的就为$m^{nn-ni+nj-ij}$
最后得到答案
O(n^2logn)事件复杂度
代码
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9+7;
ll f[300];
ll quick_pow(ll x,ll k){
ll res=1;
while(k){
if(k&1)res=(res*x)%mod;
x=(x*x)%mod;
k>>=1;
}
return res;
}
ll inv(ll x){
return quick_pow(x,mod-2);
}
ll C(int n,int m){
return ((f[n]*inv(f[n-m]))%mod*inv(f[m]))%mod;
}
int main(){
f[0]=1;
f[1]=1;
for(int i=2;i<300;i++)f[i]=(i*f[i-1])%mod;
int n,m;
ll ans = 0;
scanf("%d %d",&n,&m);
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
ll add = C(n,i)*C(n,j)%mod;
add=(add*quick_pow(m-1,n*i+n*j-i*j))%mod;
add=(add*quick_pow(m,n*n-n*i-n*j+i*j))%mod;
if((i+j)%2==0)ans=(ans+add)%mod;
else ans=(ans-add+mod)%mod;
}
}
printf("%lld\n",ans);
}
|
D
题意
一个函数f(n)就是把一个数n拆成两个部分相乘，但是这两个部分不能含有完全平方数。f(n)的值就是拆分的方法数.
思路
我们发现当数分解后质数有3次方的为0，2次方的则会使原来的少一半。1次方则会翻倍。然后利用欧拉筛处理出每个f的值就可以了。
代码
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e7+10;
int prime[N],cnt;
bool vis[N];
ll f[N];
int k[N];
void init(){
f[1]=1;
for(int i=2;i<N;i++){
if(!vis[i])prime[cnt++]=i,f[i]=2;
for(int j=0;j<cnt&&i*prime[j]<N;j++){
vis[i*prime[j]]=true;
if(i%prime[j]==0){
if(i%(1ll*prime[j]*prime[j])==0)f[i*prime[j]]=0;
else f[i*prime[j]]=f[i]/2;
break;
}
f[i*prime[j]]=f[i]*2;
}
}
}
int main(){
init();
for(int i=1;i<N;i++)f[i]+=f[i-1];
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
printf("%lld\n",f[n]);
}
}
|
E
题意
从序列种找出满足
的对数(i,j)
思路
显然不可能让我们N^2找，所以要简化式子
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
map<ll,int>mp;
ll getnum(ll x){
return 1ll*x*(x-1)/2;
}
int main(){
int n,p,k;
scanf("%d %d %d",&n,&p,&k);
for(int i=0;i<n;i++){
ll x;
scanf("%lld",&x);
mp[(((x*x)%p*((x*x)%p))-(k*x)%p+p)%p]++;
}
ll ans=0;
for(auto k:mp){
ans+=getnum(k.second);
}
printf("%lld\n",ans);
}
|
Q
题意
思路
首先分析u函数，它是一个积性函数，但是不是一个完全积性函数，然后想想当gcd(i,n)!=1时，那么他们相乘起来$\mu(in)=0$因为有>1的幂次出现。所以我们要求的就变成
对面右边第二部分式子和一开始我们要求的式子，发现没区别，于是就可以递归求解了，出口即为m==1时，返回$\mu(i)$的前缀和，$\mu(i)$的前缀和可以用很简单的杜教筛处理复杂度为
$O(\frac{n^{\frac{3}{4}}}{logn})$
代码
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+10;
ll prime[N],cnt,mu[N],summu[N];
bool vis[N];
map<ll,ll>Sumu;
void init(){
mu[1]=1;
for(int i=2;i<N;i++){
if(!vis[i])prime[cnt++]=i,mu[i]=-1;
for(int j=0;j<cnt&&i*prime[j]<N;j++){
vis[i*prime[j]]=true;
if(i%prime[j]==0){
mu[i*prime[j]]=0;
break;
}
mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<N;i++)summu[i]=summu[i-1]+mu[i];
}
ll getans(ll x){
if(x<N)return summu[x];
if(Sumu[x])return Sumu[x];
ll res=1;
for(ll l=2,r;l<=x;l=r+1){
r=x/(x/l);
res-=(r-l+1)*getans(x/l);
}
return Sumu[x]=res;
}
ll getmu(ll n){
if(n<N)return mu[n];
ll res=1;
for(ll i=2;i*i<=n;i++)
if(n%i==0)
{
if(n%(i*i)==0)return 0;
res*=-1,n/=i;
}
if(n>1)res*=-1;
return res;
}
ll solve(ll n,ll m){
if(n==1)return getans(m);
ll res=getmu(n);
if(res==0)return 0;
ll add=0;
for(ll i=1;i*i<=n&&i<=m;i++){
if((n%i)==0){
add+=(getmu(i)*solve(i,m/i));
if(1ll*i*i!=n&&n/i<=m)add+=(getmu(n/i)*solve(n/i,m/(n/i)));
}
}
return res*add;
}
int main(){
ll n,m;
init();
scanf("%lld %lld",&m,&n);
printf("%lld\n",solve(n,m));
}
|