大数幂模---欧拉降幂/java/Python

作者: ffffffffffffly | 来源:发表于2019-01-30 21:16 被阅读0次

大数幂模---欧拉降幂/java/Python
Codeforce-Power Tower(欧拉降幂)
欧拉函数 || 降幂
super_log(欧拉降幂)
神奇的“降幂”思维
快速幂取余
RSA
POJ1001
杜教筛
逆向-RSA加密

2019牛客网寒训4场#E

题目描述

精通程序设计的 Applese 叕写了一个游戏。
在这个游戏中，有一个 n 行 m 列的方阵。现在它要为这个方阵涂上黑白两种颜色。规定左右相邻两格的颜色不能相同。请你帮它统计一下有多少种涂色的方法。由于答案很大，你需要将答案对 10^9+7取模。

输入描述:

仅一行两个正整数 n, m，表示方阵的大小。

输出描述:

输出一个正整数，表示方案数对 10^9+7取模。

示例1

输入
1 1

输出
2

示例2

输入
2 2

输出
4

备注:

1 ≤ n, m ≤ 10^100000

C++解法：
首先，推导一下可知每一行都只有2中涂色方法，一共有n行，所以答案是 $2^{n}$ 。但是n为高精度的数，用long long 根本存储不了，所以只能用字符串str存储，再计算 $2^{str}$ ，指数非常大，所以直接快速幂模是不行了，用到了欧拉降幂公式（扩展欧拉定理），由题意2和 $10^9+7$ 互质，所以 $a^{q} \equiv a^{q mod \varphi (m)} (mod m)$ ，问题转化成求str的数和 $\varphi(m)$ 的值，而 $10^9+7是素数，可以直接$ $\varphi(m) = m-1$ ，求字符串的代表数可以迭代，从高位到低位，（当前位*10+下一位）%（m-1），最后再用快速幂模。

代码：

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const ll m = 1e9+7;
/*
ll Euler(ll n)
{
    ll r = n;
    for(int i=2; i*i <= n; ++i){
        if(n%i == 0){
            r = r / i *(i-1);
            while(n%i == 0)
                n /= i;
        }
    }
    if(n > 1) r = r/n * (n-1);
    return r;
}
*/
ll quick_mod(ll a, ll b, ll c)
{
    ll ans = 1;
    while(b){
        if(b & 1)
            ans = ans * a % c;
        a = a * a % c;
        b >>= 1;
    }
    return ans % c;
}

int main()
{
    string str, str1;
    ll ans;
    while (cin >> str >> str1){
        int len = str.length();
        ans = (str[0]-'0') % m;
        for(int i=1; i<len; ++i){
             ans = (ans*10 + str[i] - '0') % (m-1);
        }
        cout << quick_mod(2, ans, m) << endl;
    }
    return 0;
}

java解法：直接调用BigInteger大数类中的modPow(n,m)方法（听说很强），不过要注意各个数字都要初始化为大数类，不然好像不能编译。

AC代码

import java.util.Scanner;
import java.math.BigInteger;
public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner (System.in);
        BigInteger N = new BigInteger("1000000007");
        BigInteger a = new BigInteger("2");
        while(scan.hasNext()){
            BigInteger n = scan.nextBigInteger();
            BigInteger m = scan.nextBigInteger();
            System.out.println(a.modPow(n, N));
        }
    }
}

Python解法：最牛的！！不过说比赛不能用python，所以就平时可以用着玩下。以下代码是复制别人的，看着学习学习：

代码1

print(pow(2, int(input().split()[0]), 10**9 + 7))

代码2

n, m = map(int, input().split())
 
mod = int(1e9 + 7)
 
n %= (mod - 1)
res, x = 1, 2
 
while n > 0:
    if n % 2 > 0:
        res = res * x % mod
    x = x * x % mod
    n //= 2
 
print(res)