codeforce round499 div2

codeforces rd499 div2

比赛链接

D

交互题
队友有个条件写错了,1A。

E

数论,相似的题目SGU140
n个数的翡蜀定理

题解

问题转化为:
\(a_1·x_1+a_2·x_2+\dots+a_n·x_n = p(mod k)\)问p的集合, \(x_i\)是未知数
首先考虑两个未知变量:
\(a_1·x_1+a_2·x_2=s·gcd(a_1, a_2)\), 表示\(a_1·x_1+a_2·y_2\)可以表示\(gcd(a_1, a_2)\)的倍数

那么原来的式子就转化为\(a_1·x_1+a_2·x_2+\dots+a_n·x_n + t·k\)表示\(a_1, a_2, a_3, \dots, a_n, k\)的倍数,那么p必须也是这n+1个数的公共的倍数。问题得以求解。

ac code

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;
const int maxn = 1e5+10;
int a[maxn];
int n, k;
int main(){
ios::sync_with_stdio(false);
cin>>n>>k;
for(int i=1; i<=n; i++){
cin>>a[i];
}
int common = a[1];
a[n+1] = k;
for(int i=2; i<=n+1; i++){
common = __gcd(common, a[i]);
}
int tot = 0;
bool flag = false;
if(k%common == 0) flag = true;
tot += k/common;
cout<<tot<<endl;
if(flag) cout<<0<<" ";
for(int i=1; common*i<k; i++){
cout<<common*i<<" ";
}
cout<<endl;
return 0;
}

问题升级

SGU140
要求求出所有的\(x_i\)的集合,要求非负
题解
相当于在前面的基础之上再倒回来求一遍

ac code

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
#define N 110
using namespace std;
LL ex_gcd(LL a,LL b,LL &x,LL &y) //拓展欧几里得
{
if(b==0)
{
x=1; y=0;
return a;
} else
{
LL r=ex_gcd(b,a%b,y,x);
y-=x*(a/b); return r;
}
}
LL x[N],y[N],ans[N];
int n,p,b,a[N];
int main()
{
scanf("%d%d%d",&n,&p,&b);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]%=p;
}
LL gcd=a[1]; a[n+1]=p; //最后一次是k*gcd(x1,x2,……,xn)+kp=0
for(int i=1;i<=n;i++)
gcd=ex_gcd(gcd,a[i+1],x[i],y[i]); //记录下每一次的两个系数x和y
if (b%gcd) {puts("NO"); return 0;}
puts("YES");
gcd=b/gcd; y[0]=1;
for(int i=n;i>0;i--)
{
gcd=(gcd*x[i]%p+p)%p; //这相当于k*gcd中的k
ans[i]=(gcd*y[i-1]%p+p)%p; //结果还要乘以上一项中的y
}
for(int i=1;i<n;i++)
printf("%lld ",ans[i]);
printf("%lld\n",ans[n]);
return 0;
}

n维拓展欧几里得的板子

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
49
50
51
52
53
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
#define N 110
using namespace std;
LL ex_gcd(LL a,LL b,LL &x,LL &y) //拓展欧几里得
{
if(b==0)
{
x=1; y=0;
return a;
} else
{
LL r=ex_gcd(b,a%b,y,x);
y-=x*(a/b); return r;
}
}
LL x[N],y[N],ans[N];
int n,p,b,a[N];
int main()
{
scanf("%d%d%d",&n,&p,&b);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]%=p;
}
LL gcd=a[1]; a[n+1]=p; //最后一次是k*gcd(x1,x2,……,xn)+kp=0
for(int i=1;i<=n;i++)
gcd=ex_gcd(gcd,a[i+1],x[i],y[i]); //记录下每一次的两个系数x和y
if (b%gcd) {puts("NO"); return 0;}
puts("YES");
gcd=b/gcd; y[0]=1;
for(int i=n;i>0;i--)
{
gcd=(gcd*x[i]%p+p)%p; //这相当于k*gcd中的k
ans[i]=(gcd*y[i-1]%p+p)%p; //结果还要乘以上一项中的y
}
for(int i=1;i<n;i++)
printf("%lld ",ans[i]);
printf("%lld\n",ans[n]);
return 0;
}

F

未解决的问题

文章目录
  1. 1. D
  2. 2. E
    1. 2.1. 题解
    2. 2.2. ac code
    3. 2.3. 问题升级
      1. 2.3.1. ac code
      2. 2.3.2. n维拓展欧几里得的板子
  3. 3. F
  4. 4. 未解决的问题
{{ live2d() }}