Less is more.
大意：在 [1,n] 中选出 k 个数，求这 k 个数的最大的 gcd
最近热爱写数论题不知道为什么
思路：当一个数是另一个数的倍数时，他们的 gcd 是其中小的那个数，因此想让 gcd 最大，这些选出来的数字必须满足倍数关系，又由于要选 k 个人，因此选出来人的编号应分别为 \lfloor n/k\rfloor ， 2\lfloor n/k\rfloor ， 3\lfloor n/k\rfloor ……所以最大的 gcd 应为 \lfloor n/k\rfloor。所以答案就是 \lfloor n/k\rfloor，复杂度 O(1)
代码：
#include <cstdio>
int main()
{
int n,k;
scanf("%d %d", &n, &k);
printf("%d\n", n/k);
return 0;
}
大意：给出 x_0, y_0 ，求出满足 \gcd(P,Q)=x_0,\operatorname{lcm}(P, Q)=y_0的 P,Q 的个数
挨个枚举即可，从 x_0 枚举到 y_0 ，具体思路是以下关系：
\gcd(a,b)\times\operatorname{lcm}(a,b)=\lvert ab\rvert
算出枚举到的 \gcd 然后用 x_0y_0 去除判断 lcm 是否符合条件即可。这题的数据范围理论上可以爆 int 但是他没有爆。管他的代码规范最重要。
下面的代码可以优化，但是我不想再优化了，老是 WA
#include <cstdio>
#include <cmath>
typedef unsigned long long ll;
ll gcd(ll x, ll y)
{
if(!y) return x;
return gcd(y,x%y);
}
int main()
{
ll x0,y0;
scanf("%llu %llu",&x0,&y0);
ll prod=x0*y0,ans=0;//x_0y_0
for(ll i=x0;i<=y0;i++)
{
if(!(prod%i))
{
ll gcdcur=gcd(i,prod/i);
if(gcdcur==x0 && prod/gcdcur==y0)
ans++;
}
}
printf("%llu\n",ans);
return 0;
}
高精求两数 gcd
使用辗转相除法求gcd的话不仅不方便实现高精，而且容易 T ，所以这里使用更相减损术。
老祖宗的方法真香
具体思路：
\begin{aligned}
\gcd(a,b)&=2\gcd(a/2,b/2)\quad&(2\mid a, 2\mid b)\
\gcd(a,b)&=\gcd(a/2,b)\quad&(2\mid a,2\not\mid b)\
\gcd(a,b)&=\gcd(a-b,b)\quad&(2\not\mid a,2\not\mid b,a>b)
\end{aligned}
依次解下去就可了，注意高精即可，代码有点麻烦，不要用递归容易爆栈
这题我一开始提交的时候莫名RE，结果发现是判断函数cmp写挂了，表示绝望调了好久qwq。
#include <cstdio>
#include <vector>
#include <cctype>
#include <algorithm>
using namespace std;
typedef vector<int> bigint;
bigint _minus(bigint, bigint);
bigint _times(bigint, bigint);
void div2(bigint&);
void print(bigint);
inline bool isodd(bigint&);
bigint _minus(bigint a, bigint b)//高精减法
{
for(int i=0;i<b.size();i++)
{
a[i]=a[i]-b[i];
if(a[i]<0)
{
a[i+1]--;
a[i]+=10;
}
}
for(int i=b.size();i<a.size();i++)
{
if(a[i]<0)
a[i+1]--,a[i]+=10;
}
for(int i=a.size()-1;i>0;i--)
{
if(a[i])
break;
if(!a[i])
a.pop_back();
}
return a;
}
bigint _times(bigint a, bigint b)//高精乘法
{
bigint ans;
int la=a.size(),lb=b.size();
for(int i=0;i<la+lb;i++)
ans.push_back(0);
for(int i=0;i<lb;i++)
{
for(int j=0;j<la;j++)
{
ans[i+j]+=a[j]*b[i];
if(ans[i+j]>=10)
{
ans[i+j+1]+=ans[i+j]/10;
ans[i+j]%=10;
}
}
}
for(int i=ans.size()-1;i>0;i--)
{
if(ans[i])
break;
else
ans.pop_back();
}
return ans;
}
void div2(bigint &a)
{
for(int i=a.size()-1;i>=0;i--)
{
if(a[i]&1)
a[i-1]+=10;
a[i]/=2;
}
if(!a.back())
a.pop_back();
}
bigint read()
{
bigint ans;
char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c))
{
ans.push_back(c-'0');
c=getchar();
}
reverse(ans.begin(),ans.end());
return ans;
}
void print(bigint a)
{
for(int i=a.size()-1;i>=0;i--)
printf("%d",a[i]);
printf("\n");
return;
}
inline bool isodd(bigint &a)//判断其是否为奇数
{
return a.front()&1;
}
bool cmp(bigint a, bigint b)//return a>b
{
if(a.size()>b.size())
return true;
else if(a.size()<b.size())
return false;
else
{
for(int i=a.size()-1;i>=0;i--)
if(a[i]>b[i])
return true;
else if(a[i]!=b[i])
return false;
}
return false;
}
int main()
{
bigint a=read(),b=read();
bigint tag={1},two={2};
while(a!=b)//当a=b时zhong
{
if(!isodd(a) && !isodd(b))
{//如果都是偶数那就都除以二然后标签乘二
div2(a);
div2(b);
tag=_times(tag,two);
}
else if(!isodd(a))//如果a是偶数
div2(a);//除以二
else if(!isodd(b))//如果b是偶数
div2(b);//除以二
else
{
if(cmp(a,b))//判断哪个更大然后辗转相减
a=_minus(a,b);
else
b=_minus(b,a);
}
}
print(_times(a,tag));//返回的是最终结果乘上tag
return 0;
}