Skip to content

S2OJ - 1238. Simple

题解712 字
# S2OJ # 数学 # 2018 # 常中集训
检测到 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,q≤100n, m, q \leq 100；
  • 对于 60%60\% 的数据，n,m,q≤105n, m, q \leq 10^5；
  • 对于 100%100\% 的数据，n≤105,m≤109,q≤1018,T≤10n \leq 10^5, m \leq 10^9, q \leq 10^{18}, T \leq 10。

#思路

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

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

y=c−nxm(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) 时会重复，那么只需枚举 yy 到 min⁡(lcm(n,m),q)/m\min(\text{lcm}(n, m), q) / m 即可。

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

#代码

AC 代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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 分）
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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;
}