题解 P1771 【方程的解_NOI导刊2010提高（01）】

· · 题解

emmm... 一道数论

思路

先用快速幂求出g(x)的值,问题就可以转化为一道求解不定方程:a_{1} + a_{2} + \cdot \cdot \cdot + a_{k} = g(x) 的解。

主要过程

对于一个方程,解的个数满足: C^{k-1}_{g[x]-1}

证明过程

先来观察题目中的样例:a_{1}+a_{2}+a_{3}= 4

就是将给g(x)进行拆分分成 3 个正整数.

考虑使用隔板法

从三个位置中选取两个位置可以等效为排列组合问题,即 C_{3}^{2} = 3 所以最终的答案就是 3

然后对于任意一个组合,都可以采用隔板法的思路.将其变为一个排列组合问题.

注意事项

  1. 只有对于40%的数据答案范围在long long范围以内,需要高精乘法和高精除法(可以不用除法)
  2. 注意无论是g(x)还是k都需要减1在进行计算

核心代码

  1. 高精度乘法(这个可能都会)
    for(register int i = m ; i > n ; i--){//从n+1乘到m
        for(register int j = cnt ; j >= 1 ; --j){//每一位都乘上i
            ans[j] *= i;
            if(ans[j] >= 10000 ) ans[j+1] += (ans[j]/10000);
            ans[j] %= 10000;
        }
        if(ans[cnt+1] > 0) cnt++;//高精度位数增加
    }
  1. 高精度除法(这个可能会的不多) 
    for(register int i = 2 ; i <= m-n ; i++){//从2除到m-n
    for(register int j = cnt ; j >= 1 ; --j){//每一高精度位都除i
        if(ans[j] % i){
            long long k = ans[j]%i;//找余数
            ans[j] -= k;//减去余数
            ans[j-1] += (k*10000);//后一位加上余数
        }
        ans[j] /= i;//当前一位一定可以整除了
    }
    if(ans[cnt] == 0) cnt--;//位数减少
}

关于高精度除法的说明

对于一个数\overline{abcde}用高精度储存则为:\overline{ab} \times 1000 + \overline{bcd}

那么\overline{abcde} \div \overline{k} 就可以转化为:(\overline{ab} \times 1000 + \overline{bcd})\div \overline{k}

设 \overline{ab} \div \overline{k} = n \cdots m , 那么(\overline{ab} \times 1000 + \overline{bcd})\div \overline{k} = \overline{n} \times 1000 + ( \overline{mcde} \div \overline{k} )

对于每一位都往后加,就可以进行高精度除法了

最后附上AC代码

#include <iostream>
#include <cstdio>
using namespace std;
const int mod = 1e3;
long long read(){//快读
    char ch = getchar();
    bool flag = true;
    while(ch < '0' || ch > '9'){
        if(ch == '-') flag = false;
        ch = getchar();
    }
    long long k = ch - '0';
    while(ch = getchar(),ch <= '9' && ch >= '0' ){
        k = (k<<1)+(k<<3);
        k += (ch-'0');
    }
    return flag ? k : -k;
} 
long long kuai(long long num , long long k){//快速幂
    if(k == 1) return num%mod;
    if(k & 1){//奇数
        --k;
        long long now = kuai(num,k>>1)%mod;
        return now*now%mod*num%mod;
    }
    else {//偶数
        long long now = kuai(num,k>>1)%mod;
        return now*now%mod;
    }
}
long long ans[1000],cnt=1;//cnt表示位数
int main(){
    long long k=read(),x=read();
    long long g = kuai(x%mod,x);
    long long n = k-1,m=g-1,w=m-n;
    ans[1]=1;
    for(register int i = m ; i > n ; i--){//由n+1乘到m
        for(register int j = cnt ; j >= 1 ; --j){//每一位都乘上i
            ans[j] *= i;
            if(ans[j] >= 10000 ) ans[j+1] += (ans[j]/10000);//若大于10000 大于部分移动至下一个高精位
            ans[j] %= 10000;
        }
        if(ans[cnt+1] > 0) cnt++;//位数增加
    }
    for(register int i = 2 ; i <= m-n ; i++){//从2除到m-n
        for(register int j = cnt ; j >= 1 ; --j){//将每一位都除i
            if(ans[j] % i){
                long long k = ans[j]%i;
                ans[j] -= k;
                ans[j-1] += (k*10000);//将余数移动至下一个高精位
            }
            ans[j] /= i;
        }
        if(ans[cnt] == 0) cnt--;//位数减少
    }
    printf("%lld",ans[cnt]);//前一段单独输出（第一段不含0即不能为0004）
    for(int t = cnt-1 ; t >= 1 ; t--)
        printf("%04lld",ans[t]);//这里存的是4位
    return 0;
}