HDU1014 Uniform Generator (数论)

原题地址：

题意

给出STEP和MOD的值，问能否通过给出的式子得到1到mod-1的全部数。

思路

其实只需要判断两个数是否互质就可以了，判断互质只需要使用辗转相除法判断最大公约数是否为1即可。

辗转相除法：

用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

PS:这题的输出格式有毒。。。

AC代码

#include <bits/stdc++.h>

using namespace std;

/**
 *  Created with IntelliJ Clion.
 *  @author  wanyu
 *  @Date: 2018-02-25
 *  @Time: 23:10
 *  To change this template use File | Settings | File Templates.
 * 
 */


int a, b;

bool prime() {//辗转相除法
    bool flag;
    int dividend = max(a, b);
    int divisor = min(a, b);
    while (true) {
        int temp = dividend % divisor;//看能否整除
        if (temp == 0) {//如果能够整除看除数是否为1
            flag = divisor == 1;
            break;
        }
        dividend = divisor;
        divisor = temp;

    }
    return flag;
}

int HDU1014() {
    while (~scanf("%d %d", &a, &b)) {
        bool flag = prime();
        if (flag) {
            printf("%10d%10d    Good Choice\n\n", a, b);
        } else {
            printf("%10d%10d    Bad Choice\n\n", a, b);
        }

    }
    return 0;
}