C++习题法师为了战胜妖魔,准备好了可以记为1,2,……,N的N类符咒字法师为了战胜妖魔,准备好了可以记为1,2,……,N的N类符咒字,每类符咒字有能量值p1,p2,.,pN.符咒字有足够多个,法师可以一次接

Question

C++习题 法师为了战胜妖魔,准备好了可以记为1,2,……,N的N类符咒字
法师为了战胜妖魔,准备好了可以记为1,2,……,N的N类符咒字,每类符咒字有能量值p1,p2,.,pN.符咒字有足够多个,法师可以一次接一次地扔出符咒字,连续K个符咒字就形成一个符咒词.符咒词有极强的打击妖魔的力量,但也有一些伤害法师自身的副作用.符咒词副作用计算方法是：设符咒词是X1,X2,……,Xk,对应的能量值是p1,p2,.,pk ,则副作用引起的伤害值是p1@p2@,.,@pk.这里@是一种特殊的求“最大公因”的计算,约定如下：计算p1@p2的值,应先转换p1和p2为两个二进制数,用这两个二进制数各位为系数构造系数只能为0或1的多项式,在模2计算条件下计算两个多项式的最大公因式,将最大公因式的系数提出再形成二进制数,此数的值就是原p1和p2的最大公因数.例如：p1=5,p2=6,转换为二进制数是101和110,各位做系数构造得到多项式x2+1(0x项可不写)和x2+x,x2+1＝x2+2x+1=( x+1)2 (模2计算2x=0x),x2+x=x(x+1),因此最大公因式是x+1,提出系数形成二进制数是011,即数值3,这就是求得的最大公因数,即这时p1@p2=5@6=3.多个能量值做@计算可以用两个计算的结果再与下一个进行计算.你的任务是编写程序计算法师能够构造出多少个伤害值不超过给定数值的符咒词,对程序的输入是N,K,p1,p2,.,pk,各文字意义如前所述,还有D,d1,d2,.,dD,其中D是伤害值数目,d1,d2,.,dD,是预先给定的不应超过的伤害值.程序的输出是对应伤害值的D个整数,是法师能够构造出具有不超过对应伤害值的符咒词的数目.你的程序应该允许1≤N≤50000,1≤K≤5000.两个样例如下：(1) 输入2,2,1,2,2,1,2,则应输出3,4.因为这时N=2,K=2,p1=1,p2=2,共可以形成符咒词4个：11,12,21,22,前3个求伤害值做@计算得到最大公因数都是1,第4个是2,故应输出3,4.(2) 输入5,2,1,2,3,4,5,5,1,2,3,4,5,应输出17,20,23,24,25.这时是5类符咒字共可形成25个符咒词,“最大公因数”计算结果,为1有17个,为2和3的各3个,为4和5的各1个.
下面的小程序可以完成多项式普通除法,输入nu次多项式各项系数从高到低存于数组u[nu],u[nu-1],…,u[0],nv次多项式各项系数从高到低存于数组v[nv],v[nv-1],…,nv[0],输出是求得多项式除法u/v的商和余式,商是nq次多项式各项系数从高到低存于数组q[nq],q[nq-1],…,q[0],余式是nr次多项式各项系数从高到低存于数组r[nr],r[nr-1],…,q[0]:
void div(int u[],int nu,int v[],int nv,int q[],int &nq,int r[],int &nr)
{ int i,j,k;
for(k=nu-nv;k>=0;k--)
for(j=nv+k-1;j>=k;j--){q[k]=u[nv+k]/v[nv];u[j]=u[j]-q[k]*v[j-k];}
nq=nu-nv;nr=nu-nv-1; for(i=nr;i>=0;i--) r[i]=u[i];
}
此程序容易修改为求系数为二进制数的多项式除法程序,再修改求两整数最大公因数的Euclid算法来解决本题要求的求最大公因式的计算.
请编写程序 最好加上注释行

Answer 1

说了半天废话,结果是问怎么求公因数是吧.
如果是公因数的话,两数得分别从2除起,如果能除,记录并修改被除数为结果,这样继续下去.
a=45;
List i记录_a=new List();
for(int i=2;i