526互联

Codeforces Round 644 (Div. 3) D. Buying Shovels(数论)

发布时间 2023-03-22 21:37:39作者: 高尔赛凡尔娟

https://codeforces.com/contest/1360/problem/D

D. Buying Shovels

题目大意：

一个人想买正好n把铲子。店内有k种包装的铲子:第i种包装正好由i把铲子组成(1≤i≤k)。这家商店有无限数量的包装。

选择一种类型的包装，然后购买几个(一个或多个)。

为了准确得到n把铲子，需要购买的最小包装数量是多少？

input 
5
8 7
8 1
6 10
999999733 999999732
999999733 999999733
output 
2
8
1
999999733
1

详解见代码内部

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e6+10,M=4004;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    cin>>T;
    while(T--)
    {
        LL n,m;
        cin>>n>>m;
        if(n<=m) cout<<"1"<<endl;
        else if(m==1) cout<<n<<endl;
        else
        {
            //想买n个铲子，m种包装（每个包装有i个铲子）
            LL maxn=n;//初始化需要n个，也就是只买第一种
            for(int i=1;i*i<=n&&i<=m;i++)//找出处在条件内的最大公约数
            {
                if(n%i==0)
                {
                    maxn=min(maxn,n/i);
                    //如果更大的数字（另一半）也符合条件的话，也参与比较运算
                    if(n/i<=m) maxn=min(maxn,n/(n/i));
                }
            }
            cout<<maxn<<endl;
        }
    }
    return 0;
}