蒜头君在求解一个n元的高次方程:
其中:x1,x2,…,xn 是未知数,k1,k2,…,kn是系数,p1,p2,…,pn是指数。方程中所有数都一定是整数。
假设未知数 1≤xi≤M,i=1…n。你能帮蒜头君算出这个方程的整数解个数吗?
输入格式
第一行输入一个整数 n(1≤n≤4)。
第二行输入一个整数 M(1≤M≤150)。
第3行到第 n+2 行,每行输入两个整数,分别表示 ki(∣ki∣≤20)和 pi(1≤pi≤4)。两个整数之间用一个空格隔开。
输出格式
输出一行,输出一个整数,表示方程的整数解的个数。
样例输入
3
100
1 2
-1 2
1 2
样例输出
104
#include <iostream> using namespace std; int n,m; int count; int k[10],p[10]; long long in(int x,int y){ //x的y次方可能超过int范围 long long r=1; for(int i=0;i<y;i++){ r*=x; } return r; } void dsf(int x,long long y){ if(x==n){ if(y==0){ count++; //当x=n时,判断是否是此方程的解 } return; } for(int i=1;i<=m;i++){ dsf(x+1,y+k[x]*in(i,p[x])); //第x个数,未知数为i } } int main(){ cin>>n>>m; for(int i=0;i<n;i++){ cin>>k[i]>>p[i]; } dsf(0,0); cout<<count; return 0; }