2024/1/28

昨天第一次打了下cf的div2,感觉挺不简单(作息太阴间,今天力扣周赛都没起床)
在这里简单写一下div2的q2吧

题干

Jay managed to create a problem of difficulty x and decided to make it the second problem for Codeforces Round #921.
But Yash fears that this problem will make the contest highly unbalanced, and the coordinator will reject it. So, he decided to break it up into a problemset of n sub-problems such that the difficulties of all the sub-problems are a positive integer and their sum is equal to x.
The coordinator, Aleksey, defines the balance of a problemset as the GCD of the difficulties of all sub-problems in the problemset.
Find the maximum balance that Yash can achieve if he chooses the difficulties of the sub-problems optimally.
Input
The first line of input contains a single integer t (1≤t≤1e3) denoting the number of test cases.
Each test case contains a single line of input containing two integers x (1≤x≤1e8) and n (1≤n≤x).
Output
For each test case, print a single line containing a single integer denoting the maximum balance of the problemset Yash can achieve.

大意就是把x分成n份,求怎么分能让这n个数的GCD最大,然后输出这个GCD

比如10,3,最优解是分成2,2,4,GCD就是2

假如现在的公约数是d,很容易可以想到,每一项都是d的倍数的时候,d才能是公约数.
最优情况我们可以把x分成d,d,d……x−(n−1)d.

所以只要(x%d == 0)d就是满足条件的公约数,我们可以枚举得到答案,但是注意范围,O(n)复杂度,t的1e3乘以x的1e8,就是1e11显然超时.

这里就需要用到一个我们在学求质数时就知道的知识.假如求num是否为质数,朴素的想法是for(int i = 2; i x i <= num; i++)只要num%i==0就不是质数,注意这里是i范围是i x i小于num的

回到上面求公约数的时候我们也可以只遍历到i x i <= num,这样时间复杂度就是1e3乘以1e4为1e7,可以过.

另外需要注意的是遍历过程中每次会得到两个因数来检验,一个就是i,另一个是num/i

贴出代码

int x,n;
cin >> x >> n;
int ans = 1;
for(int i = 1; i * i <= x; i++)
{
    if(x%i==0)
    {
    	a = i, b = num / i; //因数为a和b
        if(n <= x/a) //如果因数为a,每份都是a,至少要分出n份
            ans=max(ans, a);
        if(n <= x/b) //如果因数为b,每份都是b,至少要分出n份
            ans=max(ans, b);
    }
}
cout << ans << '\n';