温州做网站制作哪家好,购买天猫店铺网站,临沂高端大气网站建设,手机网站建站系统链接:题目点这里
首先要知道一个数学定理裴蜀定理#xff0c;还有完全背包的基本运用#xff0c;这里只介绍前者
也可以看一下我的个人理解#xff0c;我是第一次听说这个定理#xff0c;理解可能有误差。
假设gcd(a,b)d,gcd是最大公约数的意思。即a#xff0c;b的最大… 链接:题目点这里
首先要知道一个数学定理裴蜀定理还有完全背包的基本运用这里只介绍前者
也可以看一下我的个人理解我是第一次听说这个定理理解可能有误差。
假设gcd(a,b)d,gcd是最大公约数的意思。即ab的最大公约数是daxbymxy是任意整数可正可负对于所有的m一定会被d整除即m%d0
可以尝试画出axbyz的三维立体图很显然是一个空间平面。
z是一个未知数它的取值有无数个如果在三维坐标系中看那么是所有的zz可以被gcdab整除。 换句话说axby表示的数的集合是{实数中所有的可以被gcdab整除的数}。 以下考虑ab互质 ab如果是互质的那么 g c d a b 1 gcdab1 gcdab1 那么axby可以构成所有的整数: {axby | x ∈ x\in x∈N, y ∈ y\in y∈N, a x b y ∈ axby\in axby∈N} 当xy都是正整数的时候包括0。axby不能表示的最小数是 ( a − 1 ) ∗ ( b − 1 ) − 1 (a-1)*(b-1)-1 (a−1)∗(b−1)−1 也就是说axby可以表示大于(a-1)*(b-1)-1的所有正整数 回到题目 看懂了上面的数学基础应该这个题就比较清晰了。
那我就直接上代码了不懂的评论区留言
#includeiostream
#includealgorithm
using namespace std;
const int N 1e41; //只需要比axby的最小值大1就可以了。
const int M 110;
long long int dp[N]; //dp[i]j表示取i种包子的方案数是j
//dp[i]dp[i-a[1]]dp[i-a[2]]dp[i-a[3]]....dp[i-a[n]];
//即取i种包子的方案数等于取[i-a[1]]包子的方案数[i-a[2]]包子的方案数...[i-a[n]]包子的方案数
int a[M];
int sum 0;int gcd(int a, int b) //辗转相除法
{if (a b)swap(a, b); //大的数是被除数int r a % b; //余数if (r 0)return b;else{a b;b r;}return gcd(a, b);
}int main()
{int n;cin n;int k;for (int i 1; i n; i) //找最大公约数{cin a[i];if (i 1)k a[i];elsek gcd(k, a[i]);}if (k ! 1)cout INF; //如果最大公约数不是1那么就会有无穷个数取不到。else //说明最大公约数是1那么axby的值是所有1的倍数axby此时表示整数集所有整数{sort(a 1, a n 1);dp[0] 1; //取0种包子的方案数是1即不取这个必须要有是很重要的边界初始化for (int i 1; i N; i) //枚举包子的个数{for (int j 1; j n; j) //然后更新当前包子个数的方案数{if (i - a[j] 0)break;dp[i] dp[i - a[j]];}if (dp[i] 0) //退出内嵌for循环判断i个包子的方案数是否是0如果是说明这个数不能被构成sum;}cout sum endl;}return 0;
}对裴蜀定理有兴趣的可以关注我这篇博客我会从cf和leetcode等网站更新相关内容将会以链接形式帖在本篇下面
