AT4258 [ABC112D] Partition 题解

题意简述

给定两个整数 nnmm。试构造一个正整数序列 aa,使 i=1N=M\sum\limits_{i=1}^{N} = M

gcd(a1,a2,...,aN)gcd(a_1,a_2,...,a_N) 的最大值。

解题思路

有点难想到的结论题

推理可得,所有答案 ansans 都满足 1ansnm1 \leqslant ans \leqslant \frac{n}{m}

这样,我们从大到小枚举即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,m;
void doit(int i) {
	printf("%d",i);
	exit(0);
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=m/n;i>=1;i--) 
		if(!(m%i)) doit(i);
	return 0;
}
//code by TheCedar