很纠结的一个问题

今天写题的时候，有一道题我只能过50%。

题目是求A^B%mod的值，由于A,B,mod都是10¹⁸，所以要用快速幂和快速乘。

但是提交很多遍发现也只能是这样。这是我的代码。

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;
  }
                  }

全部评论

推荐最新楼层

地平线960

e^iπ=-1 算法工程师

试一下 st.ordinaryChars('0&(30533)#39;, '9'); // 提升long精度问题,大概率是 StreamTokenizer源码处理问题st.wordChars('0&(30533)#39;, '9'); // 提升long精度问题,小概率输入数据多了某种符号 st.nextToken(); return Long.parseLong(st.sval); 替换掉 st.nextToken(); return (long) st.nval;

点赞回复分享

发布于 2024-04-27 13:20 广东

pamhip

华南理工大学 C++

java为啥不直接用大整数类

点赞回复分享

发布于 2020-05-19 15:53