方法挖掘——CF Round 528 B Div Times Mod

Wings · 2018-12-24 12:58:57 · 个人记录

题意

给出n, k，求最小的正整数x，满足(x\ Div\ k)(x\ mod\ k) = n

1≤n≤10^6, 2≤k≤1000

头脑风暴

~~第一反应爆搜，好像也没问题。~~但是我看错数据了，n \le 10^6被我看成n \le 10^9，我就想虽然答案肯定远小于O(n)，但不敢写，于是想了数学的方法。

UPD: 爆搜没有上限，是错的hhh

数学真奇妙！我爱数学！

正确解法

设r = x\ mod\ k, 则x = pk + r, p \in N，则\lfloor\frac{pk+r}{k}\rfloor r = \lfloor p + \frac{r}{k}\rfloor r = (p + \lfloor\frac{r}{k}\rfloor)r = pr = n

由于r \in [1, k), 所以枚举r得出p并计算x，取最小即可。

方法挖掘

数学的东西可以乱射设

代码实现

#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define For(i, n) for (int i = 1; i <= n; i++)
#define MEM(x, y) memset(x, y, sizeof(x));
using namespace std;

const int INF = 0x3f3f3f3f;
const int P = 1e9+7;
//const int maxn = ;

int n, k, x = INF;

int main() {
    scanf("%d%d", &n, &k);
    For (r, k-1)
        if (n % r == 0)
            x = min(x, n/r*k + r);
    printf("%d", x);
    return 0;
}