小V和方程 唯一分解定理+整数划分

小V和方程

题目就看题去吧，，

证明：设i,j,k为单质数之积(即每个质数最多被乘1次)，i,j,k的值不同，a\sqrt{i}+b\sqrt{j}=c\sqrt{m}无解。
系数a，b，c任意。两边分别平方，完后式子右边是一个整数，左边会有一项\sqrt{ij}，系数不重要，这一项是开不出来的，一定是小数，不可能开出一个整数来，因为ij是一些不同质数的积。

再回到这题，我们把m质因数分解，根号内为一单质数之积，根号外为系数a。把等式左边的每一项也都这样表示，那么左边的项中，根号内的数要么和右边根号内的数相同，要么就是0.

那么问题转化成，把右边的系数a分解成n个数。因为可能有0的情况，我们把非0的项当成有效项，那么有效项的个数可以为1-n。

问题进一步转化成为把a分解成i个非0数，求有多少种分解方案，每两种方案数字重组后不能相同。即整数划分。

整数划分，求把n分解成k个非0数的方案个数。设dp[n][k]表示这一值。有方程：
dp[i][j] = dp[i-j][j] + dp[i-1][j-1]
首先我们可以理解，把i个物品放在j个容器内，因为要求非空，首先每个容器内放1个，然后剩下i-j个物品可以放进1个，2个，，，j个容器内，每一种放法都是互不相同的。
dp[i][j] = dp[i-j][1] + dp[i-j][2] + ... + dp[i-j][j]
化简
dp[i][j] = dp[i-j][1] + dp[i-j][2] + ... + dp[i-j][j]
= dp[(i-1)-(j-1)][1] + dp[(i-1)-(j-1)][2] + ... + dp[(i-1)-(j-1)][j-1] + dp[i-j][j]
= dp[i-1][j-1] + dp[i-j][j]

void init(int n, int k){
    for(int i=1;i<=n;i++)
        dp[i][1]=1;
    for(int i=1;i<=n;i++)
        for(int j=2;j<=k;j++)    if(i>=j)
            dp[i][j] = dp[i-j][j]+dp[i-1][j-1];
    return;
}

本题AC代码

#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll dp[1005][1005];            //dp[i][j]，i分解成j个数
int n, m, a;
inline void init(int n, int k){
    for(int i=1;i<=n;i++)
        dp[i][1]=1;
    for(int i=1;i<=n;i++)
        for(int j=2;j<=k;j++)    if(i>=j)
            dp[i][j] = (dp[i-j][j]+dp[i-1][j-1])%mod;
    return;
}
inline int GetA(int m){
    int tmp = m, ans = 1;
    for (int i=2;i*i<=m;i++){
        if (tmp%i)  continue;
        int t = 0;
        while (tmp%i==0){
            t++;
            tmp /= i;
        }
        ans *= pow(i, t/2);
    }
    return ans;
}
int main(){
    scanf ("%d %d", &n, &m);
    a = GetA(m);
    ll ans = 0;
    init(a, n);
    for (int i=1;i<=n;i++)  if (a>=i)
        ans = (ans+dp[a][i])%mod;
    printf ("%lld", ans);
    return 0;
}