今天写题的时候,有一道题我只能过50%。
题目是求AB%mod的值,由于A,B,mod都是1018,所以要用快速幂和快速乘。
但是提交很多遍发现也只能是这样。这是我的代码。
import java.math.*; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; import java.util.*; public class Main { public static long num[] = new long[1023]; public static int k=0; public static void main(String args[])throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); in.nextToken(); int T = (int)in.nval; for(int t=0;t<T;t++) { in.nextToken(); long A = (long)in.nval; in.nextToken(); long B = (long)in.nval; in.nextToken(); long P = (long)in.nval; out.println(pow(A,B,P)%P); } out.flush(); } public static long pow(long A,long B,long P) { long temp=1; while(B>0) { if((B&1)==1) { temp=cheng(temp,A,P); } A= cheng(A,A,P); B>>=1; } return temp; } public static long cheng(long a, long b,long P) { long ans = 0; while (b > 0) { if ((b & 1) != 0) { ans =(ans+ a)%P; } b >>= 1; a = (a+a)%P; } return ans; } }只能过50%的样例。
后来我把StreamTokenizer输入换为Scanner输入,就给我过了???
其余一模一样,只是换了一个输入,就给我过了??
我不知道是StreamTokenizer和Scanner的区别,还是说是牛客出现了漏洞。
有没有人可以解答一下,真的不明白,这是我ac的代码。
import java.math.*; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; import java.util.*; public class Main { public static long num[] = new long[1023]; public static int k=0; public static void main(String args[])throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); while(T -- > 0) { long a = sc.nextLong(); long b = sc.nextLong(); long mod = sc.nextLong(); System.out.println(pow(a , b , mod) % mod); } } public static long pow(long A,long B,long P) { long temp=1; while(B>0) { if((B&1)==1) { temp=cheng(temp,A,P); } A= cheng(A,A,P); B>>=1; } return temp; } public static long cheng(long a, long b,long P) { long ans = 0; while (b > 0) { if ((b & 1) != 0) { ans =(ans+ a)%P; } b >>= 1; a = (a+a)%P; } return ans; } }
全部评论
(2) 回帖