分类目录归档：算法

Codeforces Round #494 (Div. 3) 1003 B题 Binary String Constructing 构建二进制字符串 题解

发表评论

简明题意：用a个0，b个1构建出长度为n=a+b的字符串s，且对于$0 < i < n$，有$s_i != s_{i-1}$的i的个数恰为x。
当时比赛的时候没做出来，估计就是要写搜索一类的就先跳过了。后来再来写这道题目。

所以今天改了三遍。没有看任何题解。第一版：递归，第二版：递推/迭代（动规），第三版：递推（动规）+滚动数组优化。真的不知道我是怎么想起来N长时间之前背包问题里的滚动数组优化了。感觉自己特别厉害好长时间都没写了这都能想的起来。第三版程序终于有了让人没有文字说明就完全看不懂想不明白的资本啦，哈哈^v^

第一版：递归，没有任何记忆化措施，所以TLE了，然后就想着把递归换成递推。

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
#include<iostream>
#include<algorithm>
using namespace std;
int a, b, x;
char str[105];
bool recusive(int curpos, int cura, int curb, int curx) {
    if (curpos == a + b) {
        if (cura == a && curb == b && curx == x) {
            str[curpos] = '\0';
            return true;
        }
        else return false;
    }
    if ((cura == a || curb == b)&&curx==x) {
        if (cura == a) {
            for (int i = curpos; i < a + b; i++)str[i] = '1';
            str[a + b] = '\0';
            return true;
        }
        else {
            for (int i = curpos; i < a + b; i++)str[i] = '0';
            str[a + b] = '\0';
            return true;
        }
    }
    //Assume curpos==0
    str[curpos] = '0';
    bool flag = false;
    if (curpos == 0 || str[curpos - 1] == '0')flag = recusive(curpos + 1, cura + 1, curb, curx);
    else flag = recusive(curpos + 1, cura + 1, curb, curx + 1);
    if (flag)return true;
    str[curpos] = '1';
    if (curpos == 0 || str[curpos - 1] == '1')flag = recusive(curpos + 1, cura, curb + 1, curx);
    else flag = recusive(curpos + 1, cura, curb + 1, curx + 1);
    if (flag)return true;
    return false;
}
int main() {
    cin >> a >> b >> x;
    recusive(0, 0, 0, 0);
    cout << str;
}

第二版：递推。没有任何优化，时间够了，但是内存不够MLE了。四个维度分别是a,b,x,上个字符串的最后一个数字是0还是1。

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<iostream>
#include<algorithm>
#include<string>
using namespace std;
int a, b, x;
string arr[101][101][201][2]; //a,b,x,
int main() {
    cin >> a >> b >> x;
    for (int i = 1; i <= a; i++)arr[i][0][0][0] = arr[i - 1][0][0][0] + '0';
    for (int i = 1; i <= b; i++)arr[0][i][0][1] = arr[0][i - 1][0][1] + '1';
    for (int k = 1; k <= x; k++) { //curx
        for (int i = 1; i <= a; i++) { //cura
            for (int j = 1; j <= b; j++) { //curb
                //Assume to place a 0
                if (arr[i - 1][j][k - 1][1] != "")arr[i][j][k][0] = arr[i - 1][j][k - 1][1] + '0';
                else if (arr[i - 1][j][k][0] != "")arr[i][j][k][0] = arr[i - 1][j][k][0] + '0';
                //Assume to place a 1
                if (arr[i][j - 1][k - 1][0] != "")arr[i][j][k][1] = arr[i][j - 1][k - 1][0] + '1';
                else if (arr[i][j - 1][k][1] != "")arr[i][j][k][1] = arr[i][j - 1][k][1] + '1';
            }
        }
    }
    if (arr[a][b][x][0] != "")cout << arr[a][b][x][0];
    else cout << arr[a][b][x][1];
}

第三版：递推+滚动数组。把第三维由201优化到只剩2。因为动规的转移方程里面只需要上一个k和当前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
28
29
30
31
32
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int a, b, x;
string arr[101][101][2][2];
inline int trans(int num) {
    if (num % 2 == 0)return 0;
    else return 1;
}
int main() {
    cin >> a >> b >> x;
    for (int i = 1; i <= a; i++)arr[i][0][0][0] = arr[i - 1][0][0][0] + '0';
    for (int i = 1; i <= b; i++)arr[0][i][0][1] = arr[0][i - 1][0][1] + '1';
    for (int k = 1; k <= x; k++) { //curx
        for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)for(int m=0;m<=1;m++)arr[i][j][trans(k)][m]=""; //Clean the rolling array to prevent unexpected error
        for (int i = 1; i <= a; i++) { //cura
            for (int j = 1; j <= b; j++) { //curb
                //Assume to place a 0
                if (arr[i - 1][j][trans(k - 1)][1] != "")arr[i][j][trans(k)][0] = arr[i - 1][j][trans(k - 1)][1] + '0';
                else if (arr[i - 1][j][trans(k)][0] != "")arr[i][j][trans(k)][0] = arr[i - 1][j][trans(k)][0] + '0';
                else arr[i][j][trans(k)][0]="";
                //Assume to place a 1
                if (arr[i][j - 1][trans(k - 1)][0] != "")arr[i][j][trans(k)][1] = arr[i][j - 1][trans(k - 1)][0] + '1';
                else if (arr[i][j - 1][trans(k)][1] != "")arr[i][j][trans(k)][1] = arr[i][j - 1][trans(k)][1] + '1';
                else arr[i][j][trans(k)][1]="";
            }
        }
    }
    if (arr[a][b][trans(x)][0] != "")cout << arr[a][b][trans(x)][0];
    else cout << arr[a][b][trans(x)][1];
}

写了我三个小时，也是挺不容易的……继续努力！写的不清楚有问题可以在下面评论问。

Codeforces Round #494 (Div. 3) 1003 A/C/D题解

发表评论

A题：非常简单，只要找重复数字的最大个数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;
int arr[105];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int tmp;
        cin>>tmp;
        arr[tmp]++;
    }
    int maxn=0;
    for(int i=1;i<=100;i++){
        maxn=max(maxn,arr[i]);
    }
    cout<<maxn;
}

C题：用个前缀和优化一下，剩下的暴力去吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int n,k;
double arr[5005];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>arr[i];
    for(int i=2;i<=n;i++)arr[i]+=arr[i-1];
    double maxavg=0,curavg;
    for(int i=k;i<=n;i++){
        for(int j=i;j<=n;j++){
            curavg=(arr[j]-arr[j-i])/i;
            maxavg=max(maxavg,curavg);
        }
    }
    printf("%.15lf",maxavg);
}

D题：把所有二的次幂数全部搞到桶里，然后按照次幂由高到低往下减，看最后能不能减到0，如果能即可，不能就不能。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int n,q;
int bucket[32];
int powarr[32];
int checkpower(int num){
    if(num==1)return 0;
    int cnter=0;
    while(num!=1){
        num/=2;
        cnter++;
    }
    return cnter;
}
void program_init(){
    powarr[0]=1;
    for(int i=1;i<=30;i++){
        powarr[i]=powarr[i-1]*2;
    }
}
int main(){
    program_init();
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int num;
        cin>>num;
        bucket[checkpower(num)]++;
    }
    for(int i=1;i<=q;i++){
        int num,cnter=0;
        cin>>num;
        for(int i=30;i>=0;i--){
            cnter+=min(num/powarr[i],bucket[i]);
            num-=min(num/powarr[i],bucket[i])*powarr[i];
        }
        if(num!=0)cout<<-1<<endl;
        else cout<<cnter<<endl;
    }
}

Codeforces 598A Tricky Sum 技巧求和

发表评论

题目地址：http://codeforces.com/problemset/problem/598/A
这道题目本来一开始是想要搞暴力的，但是第一个就超时。不得已换了个数学方法。
首先用小学生都会的数列求和：（首项+末项）*项数/2 把从1…n的和算出来，然后计算出不大于n的2的幂次共有多少个，用等比数列求和公式求出它们的和，减去两倍即可。
上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;
long long try2(long long n){ //函数try2就是计算从1到n之间所有不大于n的2的幂次之和，可结合等比数列求和公式推导后再领悟，不懂可以看下面或者评论我博客。
    long long m2=1;
    while(m2<=n)m2*=2;
    return m2-1;
}
void process(){
    long long n;
    cin>>n;
    cout<<((1+n)*n/2-2*try2(n))<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--)process();
}

其实做这道题是要数学功底的。。。我还是把具体的推导过程说一下好了。我们想要求出小于n的所有2的幂次方项之和，根据等比数列求和公式可知:2^0+2^1+2^2+…+2^n=2^{n+1}-1所以我们只要找到最大的小于n的2的幂次再乘2减1就可以了。具体代码可参见函数try2()。

Codeforces 597B Restaurant 餐厅

发表评论

题目地址：http://codeforces.com/contest/597/problem/B
和洛谷P1803一模一样，之前写过的题解：https://renjikai.com/luogu-p1803/
耻辱啊，还要看原来的题解……

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
#include<iostream>
#include<algorithm>
using namespace std;
struct ss{
    int s,e;
    bool operator < (ss s2){
        if(e!=s2.e)return e<s2.e;
        else return s>s2.s;
    }
}sa[500005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>sa[i].s>>sa[i].e;
    }
    sort(sa+1,sa+1+n);
    int cnter=0,t=0;
    for(int i=1;i<=n;i++){
        if(sa[i].s>t){
            cnter++;
            t=sa[i].e;
        }
    }
    cout<<cnter;
}

Codeforces 597A Divisibility 整除

发表评论

题目：http://codeforces.com/contest/597/problem/A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;
inline long long cal(long long a,long long b,long long k){
    return b/k-(a-1)/k;
}
int main(){
    long long k,a,b;
    cin>>k>>a>>b;
    if(a>0)cout<<cal(a,b,k);
    else if(b<0)cout<<cal(-b,-a,k);
    else if(a==0)cout<<b/k+1;
    else if(b==0)cout<<(-a)/k+1;
    else if(a<0&&b>0)cout<<cal(1,b,k)+cal(1,-a,k)+1;
}

NOIP2017 普及组第三道 棋盘

发表评论

这题写的异常难受……先想着用动态规划，难受死了，才20分。然后后来再看题解，用记忆化BFS，写的也难受，主要是太难想，终于AC了。开心~

写了有6、7个钟头吧。挺羞愧的。。。我写这种题怎么能这么长时间呢……

所有测试点全部0ms。

成就感极高。

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
#include<iostream>
#include<memory.h>
#include<queue>
using namespace std;
struct qs { //Convenient for passing parameters
    int tx, ty, os, rs, sc; //destination's coordinate (x,y) :tx,ty ;previous point::original status of color,real status of color :os,rs ;previous point's score:sc.
    qs(int tx1, int ty1, int os1, int rs1, int sc1) {
        tx = tx1; ty = ty1; os = os1; rs = rs1; sc = sc1;
    } //the init of struct
};
int m, n;
int arr[105][105], f[105][105]; //arr stores the color(status) of all coordinate; f stores the least gold the person will spend
int shiftx[4] = { 1,-1,0,0 }, shifty[4] = { 0,0,1,-1 }; //shifts for the coordinate
queue<qs> q;
void execute(qs o) {
    //Calculate New Score
    //Compare Which one is smaller
    //Only when the new one is smaller one,will the program insert the queue
    int nscore = 0x7fffffff;
    if (o.rs != -1 && arr[o.tx][o.ty] != -1) { // C2C(R2R/Y2Y/R2Y/Y2R) {"C"："Color","2":"To","R":"Red","Y":"Yellow"};
        if (o.rs == arr[o.tx][o.ty])nscore = o.sc; // R2R/Y2Y
        else nscore = o.sc + 1; // R2Y/T2R
        if (nscore < f[o.tx][o.ty] || o.tx==1&&o.ty==1) { //o.tx==1&&o.ty==1 is to create an entrance for the inital queue push
            f[o.tx][o.ty] = nscore;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], arr[o.tx][o.ty], arr[o.tx][o.ty], nscore));
        }
    }
    else if (o.os != -1 && arr[o.tx][o.ty] == -1) { // C2N
        if (o.os == 0 && o.sc + 2 < f[o.tx][o.ty]) { //Assume that the temporary color of current cell is Red
            f[o.tx][o.ty] = nscore = o.sc + 2;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 0, nscore));
            nscore += 1;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 1, nscore));
        }
        else if (o.os == 1 && o.sc + 2 < f[o.tx][o.ty]) { //Assume that the temporary color of current cell is Yellow
            f[o.tx][o.ty] = nscore = o.sc + 2;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 1, nscore));
            nscore += 1;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 0, nscore));
        }
    }
}
int main() {
    memset(arr, -1, sizeof(arr));
    memset(f, 0x7f, sizeof(f));
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        arr[x][y] = c;
    }
    f[1][1] = 0;
    q.push(qs(1, 1, arr[1][1], arr[1][1], 0));
    while (!q.empty()) {
        qs cur = q.front();
        q.pop();
        if (cur.tx > m || cur.ty > m || cur.tx < 1 || cur.ty < 1)continue;
        execute(cur);
    }
    cout << (f[m][m] == 0x7f7f7f7f ? -1 : f[m][m]) << endl;
}

NOIP2017普及组前两道水题

发表评论

T1

1
2
3
4
5
6
7
8
#include<iostream>
using namespace std;
int main() {
    double a, b, c;
    cin >> a >> b >> c;
    long long re = 0.2*a + 0.3*b + 0.5*c;
    cout << re;
}

T2

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<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
bool cmp(string s1, string s2) {
    if (s1.length() != s2.length())return s1.length() < s2.length();
    return s1 < s2;
}
int main() {
    int n, q;
    vector<string> arr;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        string tmp;
        cin >> tmp;
        arr.push_back(tmp);
    }
    sort(arr.begin(), arr.end(), cmp);
    for (int i = 1; i <= q; i++) {
        int tmpi;
        string tmp;
        cin >> tmpi >> tmp;
        bool flag = false;
        for (vector<string>::iterator ptr = arr.begin(); ptr != arr.end(); ptr++) {
            if (ptr->length() - tmp.length() <=1e9 && ptr->substr(ptr->length() - tmp.length()) == tmp) {
                flag = true;
                cout << (*ptr) << endl;
                break;
            }
        }
        if (!flag)cout << "-1" << endl;
    }
}

洛谷 P1120 小木棍 ［数据加强版］

发表评论

写的很绝望……看了三遍所有题解仍然69……

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
int n, sum = 0;
int lens[100] = { 0 };
bool visited[100] = { false };
int sums[100] = { 0 };
int o_min = 0, o_max;
vector<int> divisors;
int min_len;
inline bool dfs(int curpos, int curvalue, int groups){
    if (curvalue == min_len){
        if (groups == sum / min_len - 1)return true;
        else{
            int i;
            for (i = 1; i <= n; i++){
                if (!visited[i])break;
            }
            assert(i != n + 1);
            visited[i] = true;
            bool flag = dfs(i, lens[i], groups + 1);
            visited[i] = false;
            return flag;
        }
    }
    bool flag_finished = false;
    for (int i = curpos + 1; i <= n; i++){
        if (curvalue + lens[n] > min_len || curvalue + sums[i]<min_len)break;
        if (visited[i] || curvalue + lens[i] > min_len)continue;
        visited[i] = true;
        if (dfs(i, curvalue + lens[i], groups))flag_finished = true;
        visited[i] = false;
        if (flag_finished)return true;
        for (int j = i + 1; j <= n; j++){
            if (lens[j] != lens[i]){
                i = j - 1;
                break;
            }
        }
    }
    return false;
}
inline bool process(int min_length){
    min_len = min_length;
    visited[1] = true;
    bool flag = dfs(1, lens[1], 0);
    visited[1] = false;
    return flag;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> lens[i];
        if (lens[i] > 50){
            i--;
            n--;
        }
    }
    sort(lens + 1, lens + n + 1, greater<int>());
    for (int i = 1; i <= n; i++){
        o_min = max(o_min, lens[i]);
        sum += lens[i];
    }
    for (int i = n; i >= 1; i--){
        sums[i] = sums[i + 1] + lens[i];
    }
    o_max = sum;
    for (int i = o_min; i <= o_max / 2; i++){
        if (o_max%i == 0)divisors.push_back(i);
    }
    divisors.push_back(o_max);
    for (int i = 0; i < divisors.size(); i++){
        if (process(divisors[i])){
            cout << divisors[i];
            break;
        }
    }
}

20180811日更新：已经AC。
这题真的很麻烦，之前做过一回，69分放弃了，今天又重新做，改到了78AC22TLE，又看题解里的优化终于改到了AC。
题解：https://www.luogu.org/blog/complexity/solution-p1120
https://www.luogu.org/blog/cm-nanyi2018/solution-p1120
https://www.luogu.org/blog/ogawa/solution-p1120

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
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<functional>
using namespace std;
int n,lens[70],curLen,totSum=0;
int bucket[60],lst[60],lstPtr=0;
vector<int> possibleLen;
inline int check(){
    int i;
    for(i=1;i<=lstPtr;i++)if(bucket[lst[i]]!=0)return i;
    return i;
}
inline bool dfs(int lstPos,int len){//have already added lst[lstPos] before entering this recursive function
    if(len==totSum||len==totSum-curLen)return true;
    if(len%curLen==0){
        int i=check();
        bucket[lst[i]]--;
        bool flag=dfs(i,len+lst[i]);
        bucket[lst[i]]++;
        return flag;
    }
    int curRemain=curLen-len%curLen;
    for(int i=lstPos;i<=lstPtr;i++){
        if(lst[i]>curRemain||bucket[lst[i]]==0)continue;
        bucket[lst[i]]--;
        if(dfs(i,len+lst[i])){
            bucket[lst[i]]++;
            return true;
        }
        bucket[lst[i]]++;
        if(curRemain==lst[i])return false;
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    int maxV=0;
    for(int i=1;i<=n;i++){
        cin>>lens[i];
        if(lens[i]>50){
            i--;n--;
            continue;
        }
        bucket[lens[i]]++;
        maxV=max(maxV,lens[i]);
    }
    for(int i=50;i>=1;i--)if(bucket[i]!=0)lst[++lstPtr]=i;
    for(int i=1;i<=n;i++)totSum+=lens[i];
    for(int i=maxV;i<=totSum/2;i++)if(totSum%i==0)possibleLen.push_back(i);
    possibleLen.push_back(totSum);
    bucket[lst[1]]--;
    for(int i=0;i<possibleLen.size();i++){
        curLen=possibleLen[i];
        if(dfs(1,lst[1])){
            cout<<curLen;
            return 0;
        }
    }
}

[USACO1.2]命名那个数字 Name That Number

发表评论
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
#include<bits/stdc++.h>
using namespace std;
vector<string> Dict; //用Dict存放所有字典中的名字
string str; //给定的编号
const char * str_trans = "2223334445556667 77888999"; //使用该C-风格字符串来存放A-Z(除去Q和Z这24个字母所对应的数字)
int main(){
    ios::sync_with_stdio(false); //只用cin/cout加快IO速度
    cin >> str;
    string tmp;
    while (cin >> tmp){ //将后面所有的字符串循环读入到tmp中，再放到Vector尾，(cin>>tmp)即可以起到读入字符串的作用，也可以起到判断文件是否到达末尾。详情请阅读C++ Primer Plus。
        Dict.push_back(tmp);
    }
    int len = str.length();
    bool global_flag = false;
    for (int i = 0; i < Dict.size(); i++){ //遍历所有字典元素，因为字典元素少
        if (len != Dict[i].length())continue; //剪枝，如果字符串位数不一样就没有必要比较。
        bool flag = true;
        for (int j = 0; j < len; j++){
            if (str_trans[Dict[i][j] - 'A'] != str[j]){ //比对字典中每个字符对应的数字是否与输入的每个数字相同
                flag = false; //不相同直接跳出循环
                break;
            }
        }
        if (flag){ //相同则输出该单词
            cout << Dict[i] << endl;
            global_flag = true;
        }
    }
    if (!global_flag){ //如果没有一个单词符合要求，就输出NONE。
        cout << "NONE" << endl;
    }
}

洛谷 同余方程

发表评论
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;
long long exgcd(long long a, long long b, long long &x1, long long &y1){
    if (b == 0){
        x1 = 1; y1 = 0;
        return a;
    }
    long long x, y;
    long long r = exgcd(b, a%b, x, y);
    x1 = y;
    y1 = x - a / b*y;
    return r;
}
int main(){
    ios::sync_with_stdio(false);
    long long a, b;
    cin >> a >> b;
    long long x, y;
    exgcd(a, b, x, y);
    cout << (x + b) % b;

}

做题做的心力憔悴
20180807更新：
exgcd证明过程参见：https://renjikai.com/cpp-number-theory/

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<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    ll d = exgcd(b, a%b, y, x);
    y -= a / b * x;
    return d;
}
int main() {
    ll a, b, x, y;
    cin >> a >> b;
    exgcd(a, b, x, y);
    cout << (x%b + b) % b;
}