首页 > ACM题库 > POJ-北大 > POJ 1186 方程的解数 [解题报告] Java
2013
11-07

POJ 1186 方程的解数 [解题报告] Java

方程的解数

问题描述 :

已知一个n元高次方程:



其中:x1, x2,…,xn是未知数,k1,k2,…,kn是系数,p1,p2,…pn是指数。且方程中的所有数均为整数。

假设未知数1 <= xi <= M, i=1,,,n,求这个方程的整数解的个数。

1 <= n <= 6;1 <= M <= 150。



方程的整数解的个数小于231

★本题中,指数Pi(i=1,2,…,n)均为正整数。

输入:

第1行包含一个整数n。第2行包含一个整数M。第3行到第n+2行,每行包含两个整数,分别表示ki和pi。两个整数之间用一个空格隔开。第3行的数据对应i=1,第n+2行的数据对应i=n。

输出:

仅一行,包含一个整数,表示方程的整数解的个数。

样例输入:

3
150
1  2
-1  2
1  2

样例输出:

178

解题代码:

//* @author:
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Hashtable;
import java.util.Scanner;
public class Main
{
 static int[]k=new int[6];
 static int[]p=new int[6];
 static int n,m,mark;
 static int total;
 static Hashtable< Long,Integer>hash=new Hashtable< Long,Integer>();
 public static void main(String[] args)
 {
	int i,j;
	Scanner cin=new Scanner(System.in);
	while(cin.hasNext())
	{
        hash.clear();
	 total=0;
	 n=cin.nextInt();
	 m=cin.nextInt();
	 for(i=0;i< n;i++)
	 {
	   k[i]=cin.nextInt();
	   p[i]=cin.nextInt();
	  }
	mark=n/2;
	dfs(0,0);
	dfs2(mark,0);
	System.out.println(total);
      }		
   }

  static void dfs(int pos,long sum)
  {
   if(pos==mark)
   {
    sum*=-1;
	if(hash.containsKey(sum))
	{
	   hash.put(sum,hash.get(sum)+1);
	}
	else
	  hash.put(sum,1);
	return;
    }
    int i,j;
    long tmp;
    for(i=1;i<=m;i++)
    {
	tmp=(long)k[pos];
	for(j=0;j< p[pos];j++)
	{
	   tmp*=i;
	}
	dfs(pos+1,sum+tmp);
     }
  }

 static void dfs2(int pos,long sum)
 {
   if(pos>=n)
   {
	if(hash.containsKey(sum))
	{
		total+=hash.get(sum);
	}
	return;
    }
   int i,j;
   long tmp;
   for(i=1;i<=m;i++)
   {
	tmp=(long)k[pos];
	for(j=0;j< p[pos];j++)
	{
         tmp*=i;
	}
	dfs2(pos+1,sum+tmp);
    }
		
  }
}

  1. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  2. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  3. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.