判断互质 时间限制：C/C++1000MS， 其他语言2000MS 内存限制：C/C++256MB， 其他语言512MB 难度： 简单 描述 输入两个正整数 m 和 n，判断 m 和 n 是否互质（即最大公约数为 1），是则输出 Yes，否则输出 No。 输入描述 输入两个整数 m 和 n，中间用空格隔开。 输出描述 如互质输出 Yes，否则输出 No。 C++实现

好的，以下是 C++ 的实现代码：

#include <iostream>

using namespace std;

// 求最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int m, n;
    cin >> m >> n;
    if (gcd(m, n) == 1) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

这里的 `gcd` 函数采用了递归的方式实现，可以用辗转相除的非递归方式实现，不过两种方式本质上是等价的。

相关问题

RSA算法C/C++实现

这里提供一个简单的RSA算法的C/C++实现。

算法流程：

1.选择两个大质数p和q，计算n=p*q。

2.计算欧拉函数φ(n)=(p-1)*(q-1)。

3.选择一个整数e，1< e <φ(n)，且e与φ(n)互质。

4.计算d，使得d*e≡1(mod φ(n))。

5.公钥为(n,e)，私钥为(n,d)。

6.加密：C=M^e(mod n)。

7.解密：M=C^d(mod n)。

代码实现：

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

//计算最大公约数
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

//判断是否为质数
bool isPrime(int n)
{
    if(n <= 1)
        return false;
    for(int i=2; i<=sqrt(n); i++)
    {
        if(n%i == 0)
            return false;
    }
    return true;
}

//生成大质数
int generatePrime(int min, int max)
{
    int prime;
    do
    {
        prime = rand() % (max - min + 1) + min;
    }while(!isPrime(prime));
    return prime;
}

//计算模幂
int modPower(int a, int b, int m)
{
    int res = 1;
    while(b > 0)
    {
        if(b & 1)
            res = (res * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}

//生成公私钥对
void generateKey(int &n, int &e, int &d)
{
    int p, q, phi_n;
    do
    {
        p = generatePrime(100, 1000);
        q = generatePrime(100, 1000);
        n = p * q;
        phi_n = (p - 1) * (q - 1);
    }while(gcd(phi_n, 65537) != 1); //65537为常用值
    e = 65537;
    d = 0;
    while((d*e) % phi_n != 1)
        d++;
}

//加密
void encrypt(int n, int e, char *msg, int *cipher)
{
    int len = strlen(msg);
    for(int i=0; i<len; i++)
    {
        cipher[i] = modPower(msg[i], e, n);
    }
}

//解密
void decrypt(int n, int d, int *cipher, char *msg)
{
    int len = strlen(msg);
    for(int i=0; i<len; i++)
    {
        msg[i] = modPower(cipher[i], d, n);
    }
}

int main()
{
    int n, e, d;
    generateKey(n, e, d);
    cout << "公钥：" << "(" << n << "," << e << ")" << endl;
    cout << "私钥：" << "(" << n << "," << d << ")" << endl;

    char msg[100];
    cout << "请输入要加密的明文：";
    cin.getline(msg, 100);
    int cipher[100];
    encrypt(n, e, msg, cipher);
    cout << "密文：";
    for(int i=0; i<strlen(msg); i++)
    {
        cout << cipher[i] << " ";
    }
    cout << endl;

    char dec[100];
    decrypt(n, d, cipher, dec);
    cout << "解密后的明文：" << dec << endl;

    return 0;
}

这个实现中使用了随机生成质数的方法，生成的质数范围在100到1000之间。公钥中的e取65537，私钥中的d通过枚举计算得到。加密和解密过程中使用了模幂运算。整个程序可以编译运行，输入要加密的明文，即可得到加密后的密文和解密后的明文。

c++判断是否互质代码

在C++中，判断两个整数是否互质（即最大公约数为1），可以使用欧几里得算法（也称为辗转相除法）。下面是一个简单的示例代码：

#include <iostream>
using namespace std;

// 欧几里得算法求最大公约数
int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

bool are_coprime(int num1, int num2) {
    return gcd(num1, num2) == 1; // 如果gcd等于1，则两数互质
}

int main() {
    int num1, num2;
    cout << "请输入两个整数：";
    cin >> num1 >> num2;
    if (are_coprime(num1, num2)) {
        cout << num1 << " 和 " << num2 << " 是互质的。" << endl;
    } else {
        cout << num1 << " 和 " << num2 << " 不是互质的。" << endl;
    }
    return 0;
}

在这个代码中，`gcd`函数递归地计算两个数的最大公约数，然后`are_coprime`函数检查这两个数的gcd是否为1，如果为1则返回`true`，表示它们互质。