第22组数学专题题解
A - A^B Mod C
传送门
思路：快速幂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qm(ll a,ll b,ll mod)
{
ll res=1;
a%=mod;
while(b){
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
int main()
{
ll a,b,mod,res;
cin>>a>>b>>mod;
res=qm(a,b,mod);
cout<<res;
return 0;
}
|
B - 逆元
思路：输出前(p-1)个数的逆元，但用常规方法会超时，但我们发现前(p-1)个数的逆元中，1~p-1各出现了一遍，于是等差数列求和得出了答案，当然i和p不互质就不存在逆元，只要p是素数就能和前面每一个数互质
要观察规律也得是知道怎么求一个数的逆元，下面我介绍三种方法：
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
| 1:扩展欧几里得算法(o(logmod),适用于所有模)
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0)
{
x=1,y=0;
return a;
}
ll ret=exgcd(b,a%b,y,x);
y-=a/b*x;
return ret;
}
ll inv(int a,int mod){
ll x,y;
ll d=exgcd(a,mod,x,y);
return d==1?(x%mod+mod)%mod:-1;
}
——————————————————————————————我是一条可爱的分割线———————————————————————————————————
2:费马小定理/欧拉定理(o(logmod),就是求a^mod-2,只适用于mod为素数)
ll qkpow(ll a,ll p,ll mod){
ll t=1,tt=a%mod;
while(p)
{
if(p&1)t=t*tt%mod;
tt=tt*tt%mod;
p>>=1;
}
return t;
}
ll inv(ll a,ll mod)
{
return qkpow(a,mod-2,mod);
}
——————————————————————————————我是一条可爱的分割线———————————————————————————————————
3:递归求逆元(o(logmod),思路和线性求逆元差不多,记住公式就完了，同样只适用于mod为素数)
ll inv(ll a,ll m)
{
return a==1?1:(m-m/a)*inv(m%a,m)%m;
}
——————————————————————————————我是一条可爱的分割线———————————————————————————————————
int main()
{
ll a,ret;
scanf("%lld",&a);
for(int i=1;i<a;i++){
ret=inv(i,a);
printf("%lld ",ret);
}
return 0;
}
|
题解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
bool isprime(ll x){
for(ll i=2;i*i<=x;i++){
if(x%i==0)
return false;
}
return true;
}
int main()
{
ll p;
while(cin>>p){
if(!isprime(p)){
cout<<"AKCniubi"<<endl;
}else{
cout<<(p-1)*p/2<<endl;
}
}
return 0;
}
|
C - 判决素数个数
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
| #include<bits/stdc++.h>
using namespace std;
bool isprime(int x){
if(x==1)
return false;
for(int i=2;i*i<=x;i++){
if(x%i==0)
return false;
}
return true;
}
int main()
{
int a,b,i,t,sum=0;
scanf("%d %d",&a,&b);
if(a>b){
t=a;
a=b;
b=t;
}
for(i=a;i<=b;i++){
if(isprime(i)){
sum++;
}
}
printf("%d",sum);
return 0;
}
|
D - 矩阵乘法
虽然咱新生还没开线性代数，但这道题咱们已经遇到不止一次了
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
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int a[110][110],b[110][110],c[110][110];
int m,p,n;
int i,j,k;
scanf("%d%d%d",&m,&p,&n);
for(i=0;i<m;i++)
for(j=0;j<p;j++)
scanf("%d",&a[i][j]);
for(i=0;i<p;i++)
for(j=0;j<n;j++)
scanf("%d",&b[i][j]);
for(i=0;i<m;i++)
for(j=0;j<n;j++){
c[i][j]=0;
for(k=0;k<p;k++){
c[i][j]+=a[i][k]*b[k][j];
}
}
for(i=0;i<m;i++){
for(j=0;j<n;j++){
printf("%d ",c[i][j]);
}
printf("\n");
}
return 0;
}
|
E - Bash游戏
思路：博弈论，还剩(k+1)个石子时，先手怎么拿都是输
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include<stdio.h>
int main()
{
int t,n,k;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);
if(n%(k+1)==0)
printf("B\n");
else
printf("A\n");
}
return 0;
}
|
F - 取石子游戏
思路：威佐夫博奕（讲的可清楚）
先手必输局势(a,b)近似满足(b-a)*1.618=a，因此只需判断两堆石子差值是否满足公式
floor是向下取整，如floor(3.9)=3，0.618是黄金比例，即(sqrt(5)-1.0)/2.0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b,k,t;
while(scanf("%d%d",&a,&b)!=EOF){
if(a>b){
t=b;
b=a;
a=t;
}
k=b-a;
t=(floor)(k*(1.0+sqrt(5))/2.0);
if(t==a)
printf("0\n");
else
printf("1\n");
}
return 0;
}
|
G - Matches Game
思路：尼姆博弈
取每一堆中火柴的情况可分为四种：
（1）如果轮到某人取火柴的时候，火柴已经没有了，那么此人输，设为P-格局
（2）如果轮到某人取火柴的时候，他能够取完火柴，那么此人赢，设为N-格局
（3）如果轮到某人取火柴的时候，他能够将当前格局转化为某个P格局，那么此格局为N-格局
（4）如果轮到某人取火柴的时候，他不能将当前格局转化为某个P格局，那么此格局为P-格局
有这样一个定理：
一个格局记为（x1,x2,…,xn)，且次序无关，此格局为 P-格局 当且仅当 x1^x2^…^xn = 0
其中^是按位异或运算，即二进制中两个位相同为0，相异为1，我们只用判断最终状态
因此不断异或，如果结果不为0，则先手胜
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include<stdio.h>
int main()
{
int n,ret;
int a[30];
while(scanf("%d",&n)!=EOF){
ret=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
ret=ret^a[i];
}
if(ret!=0)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
|
H - 互质数的个数（一）
思路：欧拉函数
pi是x分解成的质因数，如20=2 2 5，φ(20)=20*(1-1/2)(1-1/5)=8
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll oula(ll n){
ll rea=n;
for(ll i=2;i*i<=n;i++)
if(n%i==0){
rea=rea-rea/i;
do
n/=i;
while(n%i==0);
}
if(n>1)
rea=rea-rea/n;
return rea;
}
int main()
{
ll t,ret;
scanf("%lld",&t);
while(t--){
ll v;
scanf("%lld",&v);
ret=oula(v);
printf("%lld\n",ret);
}
return 0;
}
|
I - Sumdiv
思路：逆元+快速幂+约数和定理
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;
#define ll long long
ll a,b,m;
ll prime[500000],c[500000];
void divide(ll n){
for (ll i=2;i<=n/i;i++){
if (n % i==0){
prime[++m]=i;
while(n % i==0){
n/=i;
c[m]++;
}
}
}
if (n>1){
prime[++m]=n;
c[m]=1;
}
}
ll pow(ll a,ll b,ll p){
ll res=1;
while(b){
if(b&1){
res=res*a%p;
}
a=a*a%p;
b>>=1;
}
return res;
}
int main()
{
cin>>a>>b;
ll ans=1;
divide(a);
for(ll i=1;i<=m;i++){
if((prime[i]-1)%9901==0){
ans=(b%9901*c[i]%9901+1)*ans%9901;
continue;
}
ans=(pow(prime[i],b*c[i]+1,9901)-1+9901)%9901*ans%9901;
ll y=pow(prime[i]-1,9901-2,9901);
ans*=y;
ans%=9901;
}
printf("%lld",ans);
return 0;
}
|
J - The Lottery
思路：容斥原理
我一开始想用素数筛，没看到2^31，数组开大直接编译错误
搬运的题解：
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
| #include<bits/stdc++.h>
using namespace std;
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 2000+5;
const int dx[] = {0,0,-1,1,-1,-1,1,1};
const int dy[] = {-1,1,0,0,-1,1,-1,1};
using namespace std;
LL a[N];
LL GCD(LL a,LL b) {
return b==0?a:GCD(b,a%b);
}
LL LCM(LL a,LL b){
return a/GCD(a,b)*b;
}
int main()
{
LL n,m;
while(scanf("%lld%lld",&n,&m)!=EOF&&(n+m)) {
int tot=0;
for(LL i=0; i<m; i++){
LL val;
scanf("%lld",&val);
if(val>0&&val<n)
a[tot++]=val;
}
LL sum=0;
for(LL i=1; i<(1<<tot); i++) {
LL lcm=1;
LL cnt=0;
for(LL j=0; j<tot; j++) {
if(i&(1<<j)) {
lcm=LCM(lcm,a[j]);
cnt++;
}
}
if(cnt!=0){
if(cnt&1)
sum+=(n)/lcm;
else
sum-=(n)/lcm;
}
}
if(sum<0)
sum=0;
printf("%lld\n",n-sum);
}
return 0;
}
|
K - 组合数问题
思路：杨辉三角与组合数的关系
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
| #include<bits/stdc++.h>
using namespace std;
int c[2100][2100],f[2100][2100];
int t,k;
int main()
{
scanf("%d%d",&t,&k);
for(int i=1;i<=2000;i++){
c[i][i]=1;
c[i][0]=1;
}
for(int i=1;i<=2000;i++)
for(int j=1;j<i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
for(int i=1;i<=2000;i++)
for(int j=1;j<=2000;j++){
f[i][j]=f[i][j-1]+f[i-1][j]-f[i-1][j-1];
if(c[i][j]==0&&j<=i)
f[i][j]++;
}
while(t--){
int n,m;
scanf("%d%d",&n,&m);
printf("%d\n",f[n][m]);
}
return 0;
}
|
L - 同余方程
思路：扩展欧几里得
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
| #include<bits/stdc++.h>
using namespace std;
int a,q;
int x,y;
void exgcd(int a,int b)
{
if(b==0){
x=1;
y=0;
return;
}else{
exgcd(b,a%b);
int k=x;
x=y;
y=k-(a/b)*y;
}
return;
}
int main()
{
scanf("%d%d",&a,&q);
exgcd(a,q);
printf("%lld",(x+q)%q);
return 0;
}
|
