C++ solution with cycle T


  • 0
    Q
    /*
    https://leetcode.com/problems/super-pow/
    思路:1.找出余数的周期T,并且保存各个余数。
    2.因为指数很大很大,所以必须模拟除法(b/T)求出b在周期的位置,然后得到该位置所对应的余数。
    边界:考虑到ret == 0的情况防止下标为负数。
    */
    
    class Solution{
    public:
        int superPow(int a, vector<int>& b) {
    		int div = 1337;
            int T = 1;
    		bool flag = false;
    		int cpyA = a;
    		vector<int>mod;
    		mod.push_back(cpyA % div);
    		//找到周期
    		while(!flag)
    		{
    			int cpyA = ((cpyA%div) * (a%div))%div;//注意溢出,为了防止溢出将余数赋给cpyA
    			if(cpyA == mod[0])
    			{
    				flag = true;
    			}
    			else
    			{
    				mod.push_back(cpyA);
    				++T;
    			}
    		}
    		//模拟除法
    		int ret = 0;
    		int n = b.size();
    		for(int i = 0; i < n;)
    		{
    			do
    			{
    				ret = ret*10 + b[i++];
    			}while(i < n && ret < div);
    			ret %= T;
    		}
    		if(ret == 0)
    		{
    			++ret;
    		}
    		return mod[ret - 1];
        }	
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.