[Acwing] 532. 货币系统 背包||生成函数||搜索

前言

传送门 :

完全背包

线性代数 :

题目要求: ( n , a ) 等 价 于 ( m , b ) ⇔ ∀ k ∈ Z + (n,a) 等价于(m,b) \Leftrightarrow \forall k \in Z^+ (n,a)等价于(m,b)⇔∀k∈Z+

求最小的 m 使得等式成立

m m m的范围看出来是不可能超过 0 − n 0 - n 0−n 的

因此问题在于 缩小 ( n , a ) (n,a) (n,a) 即求 ( n , a ) (n,a) (n,a)的最大向量无关组

而这个又可以通过 筛法来求

因为对于每一个 a a a如果可以 被小于自己的数表示 那么这个 数就会被筛掉

CODE

// Problem: B. Update Files

// Contest: Codeforces - Educational Codeforces Round 116 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1606/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include 
using namespace std;
#define ll long long
#define endl '\n'
#define px first
#define py second

typedef pair pii;
int dxy[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
const int N  = 40;


void cal()
{

}


void solve()
{
	ll n,k;
	cin>>n>>k;

	ll sum = (k)*(k+1) /2;

    if(n == 1)
    {
        cout