蓝桥杯经典算法不定方程解法 & 蓝桥杯练习系统历届试题买不到的数目

最新推荐文章于 2024-11-13 14:27:18 发布

WalkingSeason

最新推荐文章于 2024-11-13 14:27:18 发布

阅读量229

点赞数

分类专栏：蓝桥杯蓝桥杯算法教学与培训

本文链接：https://blog.csdn.net/qq_16544311/article/details/114003465

版权

蓝桥杯同时被 2 个专栏收录

11 篇文章

订阅专栏

蓝桥杯算法教学与培训

5 篇文章

订阅专栏

蓝桥杯经典算法第六讲不定方程解法

蓝桥杯算法教学与培训_蓝桥杯经典算法第六讲不定方程解法

不定方程的一般解法

朴素算法

	public static void main(String[] args) {
		//ax+by=c
		//例如让a=4,b=-5,c=7
		for(int x=0;x<=100;x++)
			for(int y=0;y<=100;y++)
				if(4*x-5*y==7)
					System.out.println(x+","+y);
	}

可见所求范围有限且时间复杂度很高（O(n^2)）。

一般优化

考虑ax+by=c -> ax=c-by 可以找出x,y的整除关系进而从o(n2)优化至o(n)求出一组特解。

再由x=x0+bt, y=y0+at得通解。

public static void main(String[] args) {
	// ax+by=c
	// 例如让a=4,b=5,c=7
	for (int y = 0; y <= 100; y++)
		if ((7 - (-5 * y)) % 4 == 0) {//((7 - (-5 * y)) / 4)即为x
			System.out.println(((7 - (-5 * y)) / 4) + " " + y);
			break;
		}
}

对应题目

蓝桥杯练习系统试题历届试题买不到的数目

import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a=sc.nextInt(), b=sc.nextInt();
        boolean p[] = new boolean[a*b + 5];
        while (true) {
            p[0] = true;
            for (int i = 1; i <= a*b; i++) {
                if (i >= a && p[i - a])
                    p[i] = true;
                else if (i >= b && p[i - b])
                    p[i] = true;
            }
            for (int i = a*b; i >= 1; i--) {
                if (p[i] == false) {
                    System.out.println(i);
                    System.exit(0);
                }
            }
        }
    }
}