题目链接:https://nanti.jisuanke.com/t/40397
题意:给你n(2<n<10)和z(1<z<1e5),让你求出使|x^n+y^n-z^n|最小的x,y以及该表达式的值
分析:z,n这么大,无疑是要用到大数了。具体做法就是先x取1,y取z-1,之后y一点点变小,当x和y的n次方比z大之后,再固定y,一点点加x
JAVA大数模板常用函数:
valueof()函数,用来赋值
compareTo()方法返回值为int类型,就是比较两个值,如:x.compareTo(y)。如果前者大于后者,返回1,前者等于后者则返回0,前者小于后者则返回-1。
import java.util.*; import java.math.*; public class Main{ public static void main(String args[]){ Scanner cin = new Scanner(System.in); BigInteger a, b; //以文件EOF结束 while (cin.hasNext()){ a = cin.nextBigInteger(); b = cin.nextBigInteger(); //大整数运算 System.out.println(a.add(b)); //大整数加法 System.out.println(a.subtract(b)); //大整数减法 System.out.println(a.multiply(b)); //大整数乘法 System.out.println(a.divide(b)); //大整数除法(取整) System.out.println(a.remainder(b)); //大整数取模 //大整数的比较 if( a.compareTo(b) == 0 ) System.out.println("a == b"); //大整数a==b else if( a.compareTo(b) > 0 ) System.out.println("a > b"); //大整数a>b else if( a.compareTo(b) < 0 ) System.out.println("a < b"); //大整数a<b //大整数绝对值 System.out.println(a.abs()); //大整数a的绝对值 //大整数的幂 int exponent=10; System.out.println(a.pow(exponent)); //大整数a的exponent次幂 //返回大整数十进制的字符串表示 System.out.println(a.toString()); //返回大整数p进制的字符串表示 int p=8; System.out.println(a.toString(p)); } } }
JAVA结构体(JAVA没有结构体,只能借助类)排序的使用方法
import java.util.*; class mans { long acm,money,rp; } class cmp implements Comparator<mans> { public int compare(mans a,mans b) { if(a.acm==b.acm) { if(a.money==b.money) { return (int)(a.rp-b.rp); } return (int)(a.money-b.money); } return (int)(a.acm-b.acm); } } public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanf=new Scanner(System.in); mans a[]=new mans[1009]; while(scanf.hasNext()) { int n=scanf.nextInt(); for(int i=0;i<n;i++) { a[i] = new mans(); a[i].acm=scanf.nextLong(); a[i].money=scanf.nextLong(); a[i].rp=scanf.nextLong(); } Arrays.sort(a,0,n,new cmp()); for(int i=n-1;i>=0;i--) { System.out.println(a[i].acm+" "+a[i].money+" "+a[i].rp); } } } }
用sort进行字典序排序
import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; import java.util.*; class shu ///创建类 { String name;///比较时用String int mon; int hunt; } class cmp implements Comparator<shu> { public int compare(shu A, shu B) { if(A.hunt==B.hunt) { if(A.mon==B.mon) { int flag=(A.name).compareTo(B.name);///按字典序排序 if(flag==0) { return 0; } else if(flag<0) { return -1; } else { return 1; } } else { if(A.mon==B.mon) { return 0; } else if(A.mon<B.mon) { return -1; } else { return 1; } } } else { if(A.hunt==B.hunt) { return 0; } else if(A.hunt<B.hunt) { return 1; } else { return -1; } } } } public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { shu num[] = new shu[100005];///创建类数组 int n; n = in.nextInt(); for (int i = 0; i < n; i++) { num[i]=new shu();///这个地方容易漏 num[i].name=in.next(); num[i].hunt=in.nextInt(); num[i].mon=in.nextInt(); } Arrays.sort(num, 0, n, new cmp()); for (int i = 0; i < n; i++) { System.out.println(num[i].name); } } } }
然后便是本题题解代码了
import java.io.*; import java.util.*; import java.math.*; public class Exam { static int Ax,Ay; static BigInteger Adiff; static boolean compare(BigInteger a,BigInteger b) { if (b.compareTo(BigInteger.ZERO)<0) return true; return (a.compareTo(b)<0); } static void fast_solve(int n,int z) { Ax=Ay=-1; Adiff=BigInteger.valueOf(-1); boolean init=false; int pve_minpos=-1; BigInteger bzN = (BigInteger.valueOf(z)).pow(n); int min_pveY=z-1; for (int ix=1;ix<z;ix++) { BigInteger bx = BigInteger.valueOf(ix); BigInteger bxN=bx.pow(n); boolean is_neg=false; int start_y=min_pveY; for (int iy=start_y;iy>ix;iy--) { BigInteger by = BigInteger.valueOf(iy); BigInteger byN = by.pow(n); BigInteger diff=(bxN.add(byN)).subtract(bzN); int cmp=diff.compareTo(BigInteger.ZERO); if (cmp<0) is_neg=true; if (cmp>0) if (iy<min_pveY) min_pveY=iy; diff=diff.abs(); if (compare(diff,Adiff)==true) { Ax=ix; Ay=iy; Adiff=diff; } if (is_neg) { //if (ix%1000==0) // System.out.printf("~ %d %d %s\n",ix,iy, Adiff.toString()); break; } } } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int count,n,z; count=in.nextInt(); for (int i=0;i<count;i++) { n=in.nextInt(); z=in.nextInt(); fast_solve(n,z); System.out.printf("%d %d %s\n", Ax, Ay, Adiff.toString()); } } }