2020 CCPC Wannafly Winter Camp Day1H

题目

7-8 1H. 最大公约数

有三个人，A,B,C，其中 A 和 B 共享了一个神秘的数字 k，已知 1≤k≤n。

现在 A 和 C 说：“k 的值等于 x”。

C 不太信任 A，于是想向 B 确认一下 k 是否真的等于 x。B 虽然不想直接把 k 的值告诉 C，但是 B 允许 C 给出一个正整数 y（注意 y 可以大于 n），然后 B 会回答 gcd(k,y)。

现在给出 k,n，你需要帮助 C 决定这样的 y 的取值，使得 C 一定可以通过 B 的回答来判断 A 有没有撒谎。如果这样的 y 有多个，你需要输出最小的那个。

输入格式：
输入第一行是一个整数 T(1≤T≤50)。

对于每组数据，输入一行两个整数 n,k(1≤k≤n≤500)。

输出格式
对于每组数据，输出一行一个整数，表示答案。如果满足条件的 y 不存在，则输出 −1。

输入样例：
3
10 1
10 4
10 7

输出样例：
210
8
7

思路

一开始我的思路是，既然我要辨别这个数字是真是假，那么我就要保证，我给出的y，会使得gcd（k,y）在1-n中，gcd(i, y)（1<=i<=n）中是独一无二的，这样我就能分辨出来，如果gcd（k, y）是独一无二的，那么x就会等于k，如果不是独一无二的，x就不等于k，所以只要让gcd（k, y）独一无二即可，怎么才能独一无二，就是让y是k的倍数，btw，首先解释为什么样例1的10 1答案是210，首先我们要一个y，使得在1-10中gcd（1，210）是独一无二的，那么就让1-10中的质数相乘即可，这样gcd（i, 210）(2<=i<=10)都不可能为1。那么我们只要求出1-n里面有多少是k的倍数，那么我们就可以把问题转换成1，2，3…n/k中让gcd（1， y）独一无二，也就是让1-n/k的质数相乘，最后再乘上k，超出范围要用大数乘法。

代码

#include <iostream>
#include <cstdio>
#include <set>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <string>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <fstream>
#include <iomanip>
using namespace std;
#define dbg(x) cerr << #x " = " << x <<endl;
typedef pair<int, int> P;
typedef long long ll;

const int MAXN = 1000;
int prime[MAXN];
int tot = 0;
bool is[MAXN];
void init()
{
    memset(is, 1, sizeof(is));
    is[0] = is[1] = 0;
    for(int i = 2; i < MAXN; i++)
    {
        if(is[i])
        {
            prime[tot++] = i;
        }
        for(int j = 0; j < tot; j++)
        {
            if(prime[j] * i >= MAXN) break;
            is[i * prime[j]] = 0;
            if(i % prime[j] == 0) break;
        }
    }
}

struct BigInt
{
    const static int mod = 10000;
    const static int DLEN = 4;
    int a[600], len;
    BigInt()
    {
        memset(a, 0, sizeof(a));
        len = 1;
    }
    BigInt(int v)
    {
        memset(a, 0, sizeof(a));
        len = 0;
        do
        {
            a[len++] = v % mod;
            v/=mod;
        }while(v);
    }
    BigInt operator *(const BigInt &b)const
    {
        BigInt res;
        for(int i = 0; i < len; i++)
        {
            int up = 0;
            for(int j = 0; j < b.len; j++)
            {
                int temp = a[i]*b.a[j] + res.a[i+j] + up;
                res.a[i+j] = temp % mod;
                up = temp / mod;
            }
            if(up != 0)
            {
                res.a[i+b.len] = up;
            }
        }
        res.len = len + b.len;
        while(res.a[res.len-1] == 0 && res.len > 1) res.len--;
        return res;
    }

    void output()
    {
        printf("%d", a[len-1]);
        for(int i = len-2; i >= 0; i--)
        {
            printf("%04d", a[i]);
            
        }
        printf("\n");
    }
};

int main()
{
    
    int t, n, k;
    init();
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &k);
        int l, r;
        l = 1;
        r = n/k;
        BigInt ans(1);
        for(int i = l; i <= r; i++)
        {
            if(is[i])
            {
                BigInt tmp(i);
                ans = ans * tmp;
            }
        }
        BigInt temp(k);
        ans = ans * temp;
        ans.output();
    }
    return 0;
}