T137233 魔术增幅

设答案为$g$，那么肯定有$g\mid M$。

再设$M=\sum\limits_{i=1}^N a_i=g\times \sum\limits_{i=1}^N t_i$。

因为$t_i$都是正整数，所以$\sum\limits_{i=1}^n t_i \ge N$，所以$\dfrac{M}{g}\ge N$，也即$g\le \dfrac{M}{N}$。

于是答案就是在$[1,\dfrac{M}{N}]$中，能整除$M$的最大值。

从大到小枚举即可。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define IL inline

#define RG register

using namespace std;

#define RI RG int

    int n,m;

int main(){

    scanf("%d%d",&n,&m);

    for(RI i=m/n;i>=1;i--)

    if(m%i==0){

        printf("%d",i);

        break;

    }

    return 0;

}

巴特西

T137233 魔术增幅

最新文章

热门文章