Codeforces-1360D Buying Shovels


Problem

Portal


Meaning

求在k限制下, n的最少约数个数。


Solutions

Looking the code ~


Time complexity

$O(NT)$


Accepted Code

#include <iostream>
#include <algorithm>

using namespace std;

int T;

int main ()
{
    scanf("%d", &T);
    while(T -- )
    {
        int n, k;
        scanf("%d%d", &n, &k);

        if(k >= n) puts("1");
        else if(k == 1) printf("%d\n", n);
        else
        {
            int res, ans; bool flag = 1;
            for(int i = 1 ; i <= n / i && i <= k ; i ++ ) // i <= k? 包的数量(if) 或 物品的重量(else)
            {
                if(n % i == 0)
                {
                    if (n / i <= k) // 左边的约数一定比右边小
                    {
                        res = i;
                        printf("%d\n", res);
                        flag = 0;
                        break;
                    }
                    else ans = n / i; // ans维护sqrt(n)右边的包数量的最小值  右边的约数
                }
            }
            if(flag) cout << ans << endl; // 当左边的约数都不合适才用右边的最小约数
        }
    }

    return 0;
}

Author: Mrhh
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Mrhh !
评论
 Previous
Codeforces-1360F Spy-string Codeforces-1360F Spy-string
ProblemPortal Meaning给定n个字符串, 求一个字符串与n个字符串都只相差一个字符 Solutionsway1:1、所有字符串相同, 则答案就是任意一个字符串。2、字符串两两之间只差 1 位, 任意输出其中一个字符串。
Next 
ZCROJ首次ACM赛事--ZCROJ网络邀请赛I 举办赛程记录 ZCROJ首次ACM赛事--ZCROJ网络邀请赛I 举办赛程记录
赛事主办方西南科技大学 郑宇辉 比赛举办时间2020年05月11日 20:00 ~ 22:00 比赛赛制ACM(2020蓝桥杯模拟赛) 比赛题目比赛题目选自ZCROJ题库, 都是蓝桥杯历届真题, 官方测试数据, 可靠性极高。 精彩而
2020-05-11
  TOC