文档章节

超级pow(a^b,b由数组表示)Super Pow

叶枫啦啦
 叶枫啦啦
发布于 2017/12/27 19:57
字数 1011
阅读 17
收藏 0

问题:

Your task is to calculate a^b mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:

a = 2
b = [3]
Result: 8

Example2:

a = 2
b = [1,0]
Result: 1024

解决:

① 暴力破解。当数组b超过一定的范围之后Math.pow(a,b)会超出整数的范围,导致之后结果都变为0,所以,只能找更好的方法。

② 由于任意一个数都是2的次幂的和。所以,与Pow(x, n)的处理方法类似,都要对其对半缩小,但要注意每次都要对1337取余。注意,由于给定的指数b是一个一维数组的表示方法,我们要是折半缩小处理起来肯定十分不方便,所以我们采用按位来处理,比如2^23 = (2^2)^10 * 2^3, 所以我们可以从b的最高位开始,算出个结果存入res,然后到下一位是,res的十次方再乘以a的该位次方再对1337取余。

理论支持(转幂算法):

       (a^b) mod c = ((a mod c)^b) mod c ----公式1

       (x*y) mod c = ((x mod c) * (y mod c)) mod c  : 积的取余等于取余的积的取余。 -----公式2

class Solution {//9ms
    public int superPow(int a, int[] b) {
        int res = 1;
        for (int i = 0;i < b.length;i ++){
            res = (pow(res,10) * pow(a,b[i])) % 1337;
        }
        return res;
    }
    public int pow(int x,int n){
        if (n == 0) return 1;
        if (n == 1) return x % 1337;
        return (pow(x,n / 2) * pow(x,n - n /2)) % 1337;
    }
}

② 快速幂算法:

class Solution {//601ms
    public int superPow(int a, int[] b) {
        if (b.length == 0 || isZero(b)){
            return 1;
        }
        a = a % 1337;
        boolean flag = false;//标记次幂是否为奇数
        if (b[b.length - 1] % 2 == 1){
            flag = true;//次幂是奇数
        }
        div(b,2);
        int res = superPow(a,b);
        res = (res * res) % 1337;
        if (flag){
            res = (res * a) % 1337;
        }
        return res;
    }
    public boolean isZero(int[] num){//判断数组组成的整数是否为0
        for (int i = num.length - 1;i >= 0;i --){
            if (num[i] > 0){
                return false;
            }
        }
        return true;
    }
    public void div(int[] x,int y){//将次幂折半
        int tmp = 0;
        for (int i = 0;i < x.length;i ++){
            x[i] += tmp * 10;
            tmp = x[i] % y;
            x[i] = x[i] / y;
        }
    }
}

③ 快速幂算法+欧拉函数

除了1及其本身,1137只能被7和191整除,a^b有如下规律:

(1)首先,如果a有除数7和191,那么a % 1337 == 0,答案是0。

(2)如果a既没有除数7也没有191,那么a和1337是互质的,所以有 a^b%c = a^(b%phi(c))%c

即a ^ b % 1337 = a ^ (b % phi(1337)) % 1337 = a^(b % 1140) % 1337。

(3)最后,一个可能有7或191的除数,这是相似的。

【注】对正整数n欧拉函数{\displaystyle \varphi (n)}\varphi (n)是小于或等于n的正整数中与n互质的数的数目。

(1)   p^k型欧拉函数:

若N是质数p(即N=p), φ(n)= φ(p)=p-p^(k-1)=p-1。

若N是质数p的k次幂(即N=p^k),φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)。

(2)mn型欧拉函数

设n为正整数,以φ(n)表示不超过n且与n互素的正整数的个数,称为n的欧拉函数值。若m,n互质,φ(mn)=(m-1)(n-1)=φ(m)φ(n)。

(3)特殊性质:

若n为奇数时,φ(2n)=φ(n)。

对于任何两个互质 的正整数a,n(n>2)有:a^φ(n)=1 mod n (恒等于)此公式即 欧拉定理

当n=p 且 a与素数p互质(即:gcd(a,p)=1)则上式有: a^(p-1)=1 mod n (恒等于)此公式即 费马小定理

class Solution { //2ms
    public int superPow(int a, int[] b) {
        int c = 1337;
        int phi = euler(c);//1140
        int n = 0;
        for (int i = 0;i < b.length;i ++){
            n = n * 10 + b[i];
            n %= phi;
        }
        return fastPow(a,n,c);
    }
    public int fastPow(int a,int b,int c){
        a %= c;
        int res = 1;
        while(b != 0){
            if ((b & 1) != 0) res = res * a % c;//奇数
            a = a * a % c;
            b >>= 1;//除2
        }
        return res;
    }
    public int euler(int n){
        int res = n;
        for (int i = 2;i * i <= n;i ++){
            if (n % i == 0){
                res = res / i * (i - 1);
                while(n % i == 0){
                    n /= i;
                }
            }
        }
        if (n > 1){
            res = res / n * (n - 1);
        }
        return res;
    }

© 著作权归作者所有

叶枫啦啦
粉丝 16
博文 583
码字总数 400448
作品 0
海淀
私信 提问
Python-Day3知识点——深浅拷贝、函数基本定义、内置函数

一.深浅拷贝 import copy 浅拷贝 n1={'k1':'wu','k2':123,'k3':['carl',852]}n2=n1n3=copy.copy(n1)print(id(n1))print(id(n2))print(id(n3))print(id(n1['k3']))print(id(n3['k3'])) 深拷贝......

易改乾坤
2016/04/20
0
0
PoW挖矿算法原理及其在比特币、以太坊中的实现

  PoW,全称Proof of Work,即工作量证明,又称挖矿。大部分公有链或虚拟货币,如比特币、以太坊,均基于PoW算法,来实现其共识机制。即根据挖矿贡献的有效工作,来决定货币的分配。 比特币...

莫名2013
2018/06/26
0
0
44 个 Javascript 变态题解析 (上)

原题来自: javascript-puzzlers(http://javascript-puzzlers.herokuapp.com/) 读者可以先去做一下感受感受. 当初笔者的成绩是 21/44… 当初笔者做这套题的时候不仅怀疑智商, 连人生都开始怀...

呵呵闯
2016/07/20
22
0
scala map/list/array/的常用内置遍历操作总结 一点课堂(多岸学院)

scala map/list/array/的常用内置遍历操作总结 Scala 是面向函数的,所以在集合函数里,它很轻易地提供了非常丰富遍历操作,数组变换操作。这对于我们数据挖掘,爬虫,文本处理等都非常有帮助...

程伟鑫
09/11
13
0
Leetcode【372、1131】

问题描述:【Math】372. Super Pow 解题思路: 快速幂算法。计算 a^b mod 1337,a 是一个正整数,b 是一个非常大的正整数且以数组形式给出。 这道题其实是考察快速幂(取模)算法。 1、如何计...

牛奶芝麻
07/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

x002-语言元素

变量命令规则 硬性规则: 变量名由字母(广义的Unicode字符,不包括特殊字符)、数字和下划线构成,数字不能开头。 大小写敏感(大写的a和小写的A是两个不同的变量)。 不要跟关键字(有特殊...

伟大源于勇敢的开始
今天
4
0
nginx反向代理配置

nginx配置文件位置/usr/local/nginx/conf/nginx.conf 配置文件修改: # cd /usr/local/nginx/conf # vim nginx.conf server {listen 80;server_name localhost;#charset k......

行者终成事
今天
5
0
OSChina 周日乱弹 —— 这是假的,和我之前的不一样

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 小小编辑推荐:《男孩》-梁博 / 陶孟童 / 肖和东 / 高誉容 《男孩》-梁博 / 陶孟童 / 肖和东 / 高誉容 手机党少年们想听歌,请使劲儿戳(这里...

小小编辑
今天
15
1
Rust学习笔记一 数据类型

写在前面 我也不是什么特别厉害的大牛,学历也很低,只是对一些新语言比较感兴趣,接触过的语言不算多也不算少,大部分也都浅尝辄止,所以理解上可能会有一些偏差。 自学了Java、Kotlin、Python、...

MusiCodeXY
今天
5
0
Java 脚本引擎入门

Java Script Engine Java 脚本引擎可以将脚本嵌入Java代码中,可以自定义和扩展Java应用程序,自JDK1.6被引入,基于Rhino引擎,JDK1.8后使用Nashorn引擎,支持ECMAScript 5,但后期还可能会换...

阿提说说
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部