【洛谷 P1147】 连续自然数和

题目描述

对一个给定的正整数 $M$，求出所有的连续的正整数段（每一段至少有两个数），这些连续的自然数段中的全部数之和为 $M$。

例子：$1998+1999+2000+2001+2002 = 10000$，所以从 $1998$ 到 $2002$ 的一个自然数段为 $M=10000$ 的一个解。

输入格式

包含一个整数的单独一行给出 $M$ 的值（$10 \le M \le 2,000,000$）。

输出格式

每行两个正整数，给出一个满足条件的连续正整数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出行的第一个按从小到大的升序排列，对于给定的输入数据，保证至少有一个解。

样例 #1

样例输入 #1

10000

样例输出 #1

18 142 
297 328 
388 412 
1998 2002

样例输入 #2

15

样例输出 #2

1 5
4 6
7 8

方案一：枚举法

#include <bits/stdc++.h>
using namespace std;
int main(){
    int m;
    cin >> m;
    //因为m最大值为2e9,连续的数字至少为2，所以最大的可能性是m / 2;
    for (int i = 1; i <= m / 2; i++){
        int sum = 0, j;
        for (j = i; j <= m - 1; j++){
            sum += j;
            if (sum >= m){
                break;
            }
        }
        if(sum == m){
            printf("%d %d\n", i, j);
        }
    }
    return 0;
}

方案二：

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    
    for (int i = 1e5; i > 1; i--){//枚举项数
        int x = n / i - (i - 1) / 2;//首项
        if(x < 0){
            continue;
        }
        if ((x + x + i - 1) * i == n * 2){
            cout << x << " " << x + i - 1 << endl;
        }
    }
    return 0;
}

【】零钱的数量

学校安排红老师去给学生买铅笔，买完铅笔红老师直接发给学生了。当他想找学校报销的时候，他却忘记了花了多少钱，也不记得买了多少铅笔。

总所周知，大家经常只会关心钱包里面整百的钱，所以红老师记得他用了 𝑎a 张 100100 元和一些零钱，零钱加起来大于 00 不超过 100100（没有找零）。已知一支铅笔花费 𝑏b 元，那么红老师可能花费了多少钱？

输入格式

输入包含两个整数 𝑎(1≤𝑎≤10000)a(1≤a≤10000), 𝑏(10≤𝑏≤200)b(10≤b≤200)，表示小红老师用了 𝑎a 张 100100 元，铅笔的单价为 𝑏b 元。

输出格式

从小到大输出所有小红老师可能用的总钱数，一个数占一行。

如果没有可能，那就是小红老师记错了，输出一行 −1−1。

样例输入 1

3 11

样例输出 1

308
319
330
341
352
363
374
385
396

样例输入 2

2 199

样例输出 2

-1

输入：

2834 200

输出:

-1

输入：

22 169

输出:

-1

输入：

9 72

输出:

936

方案1：

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a, b;
    cin >> a >> b;
    int cnt = 0;
    for (int i = 1; i < 100; i++){
        if ((a * 100 + i) % b == 0){
            cout << a * 100 + i << endl;
            cnt++;
        }
    }
    if (cnt == 0){
        cout << -1;
    }
    return 0;
}

/*

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a, b;
    cin >> a >> b;
    int flag  = 0;
    for (int i = a*100+1; i < a*100+ 100; i++){
        if (i % b == 0){
            cout << i << endl;
            flag = 1;
        }
    }
    if (flag == 0){
        cout << -1;
    }
    return 0;
}

*/