P11184 带余除法

Earth2023 · 2024-10-15 22:08:29 · 题解

赛时暴力30分

题目传送门

题目&目的

阅读题目可知：

• 给定2个正整数n和q，其中n \div q = k，且n \mod q = r。
• 结果需要求出对于一组数据n和k，求出其所有余数的可能性。（即满足：n \div q = k \cdots\cdots r）
• 数据范围较大：对于全体数据，保证 1\le T\le 10，1\le n\le 10^{14}，0\le k\le 10^{14}。
• 根据数据范围，考虑数学解法。

思路1（WA，30pts，赛时做法）

第5次评测记录

当时脑子抽了，做了个暴力。

从1开始举出可能的q，然后看商是否匹配。

for (int j = 1; j <= n + 1; j++) {
    if (n / j == k) flag[n % j] = 1;
}  

而对于以上代码提到的flag，就是标记当前符合要求的余数，如果像这样：

if (n / j == k) ans++;

就有可能会导致：对于一个重复的余数，进行了重复计算。

最后再用一个for循环倒序遍历查找每一个flag[i] = 1的可能，并对ans自加，然后将flag[i] = 0。

for (int j = 0; j <= n + 1; j++) {
    if (flag[j]) {
        sum++;
        flag[j] = 0;    
    } 
}

完整代码如下：

#include <iostream>
using namespace std;
long long t, n, k, sum, flag[10000005];
int main() {
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cin >> n >> k;
        for (int j = 1; j <= n + 1; j++) {
            if (n / j == k) flag[n % j] = 1;
        }  
        for (int j = 0; j <= n + 1; j++) {
            if (flag[j]) {
                sum++;
                flag[j] = 0;    
            } 
        }
        cout << sum << endl;
        sum = 0;
    }
    return 0;
}

但是肯定是会TLE的。

思路2（AC，100pts）

第9次评测记录

暴力不够，数学来凑。

让我们先来研究一组数据。

在这组数据中，给定的n = 32，给定的k = 2。

看完后，我们会发现：

• 当11 \leq q \leq 16，k = 2，有6种r的可能性。
• 当q = 10时，k = 3，代表r可能性的结束。

由此，我们推断：

ans = (n / k) - (n / (k + 1));

最后再对某些情况进行特殊判断：

• k = 0

if (k == 0) {
    printf("1\n");
    continue;
}

• k = 1

考虑奇偶两种情况。

当n = 2，满足k = 1的情况的余数只有1种。 当%n = 3，满足k = 1的情况的余数有2种。 当n = 4，满足k = 1的情况的余数有2种。 当n = 5，满足k = 1$的情况的余数有3种。

综上：

1. 当n \mod 2 == 0，满足k = 1情况的余数可能只有n \div 2种。

   if (n % 2 == 0) {
   printf("%lld\n", (n / 2));
   }

2. 否则（n \mod 2 == 1），满足k = 1情况的余数可能有(n + 1) \div 2种。

   else {
   printf("%lld\n", ((n + 1) / 2));
   }

这时，此题AC代码就出来了。

AC Code

#include <iostream>
#define ll long long
ll t, n, k, ans;
using namespace std;
int main() {
    scanf("%lld", &t);
    for (int i = 1; i <= t; i++) {
        scanf("%lld%lld", &n, &k);
        if (k == 0) {
            printf("1\n");
            continue;
        } else if (k == 1) {
            if (n % 2 == 0) {
                printf("%lld\n", (n / 2));
            } else {
                printf("%lld\n", ((n + 1) / 2));
            }
            continue;
        }
        ans = (n / k) - (n / (k + 1));
        printf("%lld\n", ans);
    }
    return 0;
}

写在最后

如有某些文字或符号表述错误，请立刻告诉我！！！ 如有疑问，欢迎指出/讨论！！！

Edit time：2024/10/15 22:08:30