不知道怎么处理，答案是输入的x的一个因数，不知道怎么和n建立联系，假设刚好整除，用x除以n表示的就是答案
假设不可以整除，暴力枚举不知道如何下手，突然有一个想法，每一个容器从1开始增加，但是这样子找不到最大的公约数，从最大值开始减小呢，
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
return b>0?gcd(b,a%b):a;
}
void solve()
{
int x,n;
cin>>x>>n;
int ans=1;
if(x%n==0) ans=x/n;
else
{
int temp=x/n;
int k=temp+x%n;
int g=gcd(temp,k);
if(g!=1) ans=g;
else
{
int cnt=0;
while(g==1&&cnt<=100&&temp>=1&&temp*(n-1)+k==x)
{
cnt++;
k+=n-1;
temp--;
g=gcd(k,temp);
if(g!=1)
{
ans=g;
break;
}
}
}
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
维护最后一个元素，首先前面n-1个元素的值是temp，最后一个元素的值是k，然后每一次更新就是让前面n-1个元素每一个元素减小1，最后一个元素每次增加n-1，直到最大公约数不是1，表示找到了一个最大公约数，按道理来说所有数字都是最大的，最大公约数也是最大的
好吧有点牵强，看下题解是咋写的
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int x,n;
cin>>x>>n;
int ans=1;
if(x%n==0) ans=x/n;
else
{
for(int i=1;i*i<=x;i++)
{
if(x%i==0)
{
if(n*i<=x) ans=max(ans,i);
if(n<=i) ans=max(ans,x/i);
}
}
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
上面这份代码不小心爆int了，教训是可以使用除法的话尽量避免使用乘法
signed integer overflow
有符号整数溢出
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int x,n;
cin>>x>>n;
int ans=1;
if(x%n==0) ans=x/n;
else
{
for(int i=1;i*i<=x;i++)
{
if(x%i==0)
{
if(n<=x/i) ans=max(ans,i);
if(n<=i) ans=max(ans,x/i);
}
}
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
上面是ac代码
自己想到了答案一定是x的除数，非常难得，但是有一个关键的式子没有想出来
假设这个除数是d，那么前面n-1个元素都是d，最后一个元素是x-(n-1)*d，x可以看作kd，最后一个元素可以看作kd-(n-1)*d，这样就很明显，所有元素的最大公约数是d
数据范围给的x是1e8，用试除法 n \sqrt{n} n的时间复杂度，想试一下能不能直接遍历求答案，
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int x,n;
cin>>x>>n;
int ans=1;
if(x%n==0) ans=x/n;
else
for(int i=1;i<=x;i++)
if(x%i==0)
if(n<=x/i) ans=max(ans,i);
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
在第三个测试点超时了
第三个测试点是一些比较大的数字
每一次用max维护最大值
