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;
}
- 数论 Codeforces Shovels Buying Round数论codeforces shovels buying 数论codeforces product round 数论round codeforces dances 数论codeforces思维 数学 数论educational codeforces equalize 数论educational codeforces chains 数论codeforces admirer milena 数论codeforces absolute beauty educational codeforces round rated codeforces round 911 div