不定方程求解

题目描述

给定正整数a，b，c。求不定方程 ax+by=c 关于未知数x和y的所有非负整数解组数。

Input

一行，包含三个正整数a，b，c，两个整数之间用单个空格隔开。每个数均不大于1000。

Output

一个整数，即不定方程的非负整数解组数。

Sample

输入 2 3 8

输出 4

---

分析题目

这道题目要求解不定方程 ax+by=c，其中 a、b、c 是给定的正整数，要求求解出所有满足条件的非负整数解组数。

解决这个问题可以使用一个简单的穷举法或者更高效的方法来解决。我们来探讨一下这两种方法的思路：

简单穷举法

思路1：

1. 使用两个循环分别遍历可能的 x 和 y 的取值，假设它们都在 0 到 c/a、c/b 之间（因为 x 和 y 都是非负整数，所以它们的取值范围是 0 到 c/a、c/b）
2. 在每一组 x 和 y 的取值下，计算 ax + by 是否等于 c
3. 如果等于 c，则将结果计数器加一
4. 最终得到的计数器的值即为满足不定方程的非负整数解组数

• NOTE : 这种方法虽然非常直观的就可以求解,但是由于是嵌套循环,所以在输入较大的时候效率降低.

Java代码

package day06;

import java.util.Scanner;

public class Main {

    public static int countNonNegativeIntegerSolutions(int a, int b, int c) {
        int count = 0;
        for (int x = 0;x <= c/a;x++){
           for( int y = 0;y <= c/b;y++){
               if(a * x + b * y == c) {
                   count++;
               }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a, b, c;
        a = scanner.nextInt();
        b = scanner.nextInt();
        c = scanner.nextInt();
        int result = countNonNegativeIntegerSolutions(a, b, c);
        System.out.println(result);
        scanner.close();
    }
}

C代码

#include <stdio.h>

 int countNonNegativeIntegerSolutions(int a, int b, int c) {
     int count = 0;
     for (int i = 0; i <= c/a ; i++) {
             for (int j = 0; j <= c/b; j++) {
                 if(a*i+b*j == c){
                     count++;
                 }
             }
         }
     return count;
 }

 int main() {
     int a, b, c;
     scanf("%d %d %d", &a, &b, &c);
     int result = countNonNegativeIntegerSolutions(a, b, c);
     printf("%d\n", result);
     return 0;
 }

---

思路2

使用第一种思路的时候,两层嵌套循环中会有很多不必要的循环,我们可以通过另外一种方式来写循环条件,这种方法避免了不必要的嵌套循环，可以更快地找到满足条件的解。

1. 外层循环 for(int x = 0; x*a<=c;x++)：在循环中，我们从 x = 0 开始，逐步增加 x 的值，直到满足条件 x * a <= c 不再成立。这个条件确保我们在每次迭代中都只考虑满足方程 ax + by = c 的 x 的可能取值范围，以提高效率。

2. 条件判断 if((c-a*x)%b==0)：在每次迭代中，我们计算 (c - a * x) % b 的值，即通过已知的 x 求解出对应的 y，如果 (c - a * x) % b 的结果为 0，说明该 x 对应的 y 是整数，即满足方程 ax + by = c。因此，我们在这个条件判断中检查是否存在满足方程的 y，如果存在，则这个 x 是一个满足条件的解。

NOTE :这种循环模式的优势在于，它只需要在外层循环中遍历可能的 x 的值，然后通过简单的计算就能直接得到对应的 y 值，从而避免了内层循环的使用，提高了效率。

Java代码

package day06;

import java.util.Scanner;

public class Main11 {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int c = scanner.nextInt();

        int count = 0;
        if (a == 0 && b == 0 && c==0) {
            count++;
        }

        if (a > 1000 || b > 1000 || c > 1000) {
            System.out.println("输入的值超出范围了!");
            return;
        }

        for (int x = 0; a * x <= c; x++) {
         if ((c - a * x) % b == 0) {
             count++;
        }
     }
        System.out.println(count);
        scanner.close();
    }
}

C代码

#include <stdio.h>

 int countNonNegativeIntegerSolutions(int a, int b, int c) {
     int count = 0;
    
        for (int x = 0; a * x <= c; x++) {
         if ((c - a * x) % b == 0) {
             count++;
        }
     }
     return count;
 }

 int main() {
     int a, b, c;
     scanf("%d %d %d", &a, &b, &c);
     int result = countNonNegativeIntegerSolutions(a, b, c);
     printf("%d\n", result);
     return 0;
 }

测试结果