Skip to content

S2OJ - 1238. Simple

题解721 字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

题面

题目描述

对于给定正整数 n,mn, m,我们称正整数 cc 为好的,当且仅当存在非负整数 x,yx, y,使得 nx+my=cnx + my = c

现在给出 TT 组数据,对于每组数据,给定 n,m,qn, m, q,求 [1,q][1, q] 内有多少个正整数不是好的。

输入格式

第一行,一个整数 TT 表示数据组数。

接下来每行三个数,分别表示 n,m,qn, m, q,即一组询问。

输出格式

对于每组数据,输出一行表示答案。

输入输出样例

输入样例 #1

2
78 100 4
70 3 34

输出样例 #1

4
23

数据范围及约定

  • 对于 30%30\% 的数据,n,m,q100n, m, q \leq 100
  • 对于 60%60\% 的数据,n,m,q105n, m, q \leq 10^5
  • 对于 100%100\% 的数据,n105,m109,q1018,T10n \leq 10^5, m \leq 10^9, q \leq 10^{18}, T \leq 10

思路

先考虑将 nx+my=cnx + my = c 中的 x,yx, y 单独提出来,得到下面两个式子:

x=cmyn(1)x = \frac{c - my}{n} \tag{1}

y=cnxm(2)y = \frac{c - nx}{m} \tag{2}

可以考虑枚举 x,yx, y 之中的任意一个数,根据 (1)(1) 式或 (2)(2) 式计算出对应 y,xy, x 的值。

通过数据范围可以发现,当使用 (2)(2) 式计算时会超时。

再通过暴力打表(程序见文末)可以发现一个规律:cc 在到达 lcm(n,m)\text{lcm}(n, m) 时会重复,那么只需枚举 yymin(lcm(n,m),q)/m\min(\text{lcm}(n, m), q) / m 即可。

最后输出时需要去掉 x=0,y=0x = 0, y = 0 的情况,将 ans1ans - 1 即可。

代码

AC 代码
#include <algorithm>
#include <iostream>

using std::cin;
using std::cout;
#define endl '\n'

int t, n, m;
long long q;

inline long long lcm(int a, int b) {
    return 1ll * a * b / std::__gcd(a, b);
}

int main() {
    std::ios::sync_with_stdio(false);
    cin >> t;
    while (t--) {
        long long ans = 0;
        cin >> n >> m >> q;
        for (long long y = 0; y <= std::min(lcm(n, m) - 1, q) / m; y++) {
            ans += (q - y * m) / n + 1;
        }
        cout << q - ans + 1 << endl;
    }
    return 0;
}
暴力(60 分)
#include <iostream>
#include <set>

using std::cin;
using std::cout;
#define endl '\n'

int t, n, m, q;

int main() {
    std::ios::sync_with_stdio(false);
    cin >> t;
    while (t--) {
        int ans = 0;
        std::set<int> set;
        cin >> n >> m >> q;
        for (int i = 0; i * n <= q; i++) {
            for (int j = 0; i * n + j * m <= q; j++) {
                if (i * n + j * m <= q) {
                    set.insert(i * n + j * m);
                }
            }
        }
        cout << q - set.size() + 1 << endl;
    }
    return 0;
}