【数论】快速幂、矩阵快速幂取模专题训练

你的名字 2023-07-01 07:30 54阅读 0赞

###  ###

*  前言
 *  HDU-1061 Rightmost Digit（快速幂取模）
 *  HDU-2817 A sequence of numbers（快速幂取模）

# 前言 #

**1、快速幂模板**

//C++版本
    typedef long long ll;
    ll q_pow(ll a, ll n, ll mod) { 
    	ll ans = 1, base = a;
    	while(n) { 
    		if(n&1)		ans=ans*base%mod;
    		base=base*base%mod;
    		n>>=1;
    	}
    	return ans;
    }
    
    //Java版本
    static long q_pow(long a, long n, long mod) { 
    	long ans = 1, base = a;
    	while(n!=0) { 
    		if((n&1)!=0)		ans=ans*base%mod;
    		base=base*base%mod;
    		n>>=1;
    	}
    	return ans;
    }

**2、矩阵快速幂模板**

# HDU-1061 Rightmost Digit（快速幂取模） #

> **原题链接：**[http://acm.hdu.edu.cn/showproblem.php?pid=1061][http_acm.hdu.edu.cn_showproblem.php_pid_1061]

*  **题意：** 求 n^n%10的结果。
 *  **思路：** 快速幂取模裸题。

**Code（Java）：**

import java.util.*;
    import java.math.*;
    public class Main { 
        static long q_pow(long a, long n, long mod) { 
            long ans = 1, base = a;
            while(n!=0) { 
                if((n&1)!=0)        ans=ans*base%mod;
                base=base*base%mod;
                n>>=1;
            }
            return ans;
        }
        public static void main(String[] args) { 
            Scanner cin = new Scanner(System.in);
            int t = cin.nextInt();
            while(t-- >0) { 
                long n = cin.nextLong();
                System.out.println(q_pow(n,n,10));
            }
        }
    }

# HDU-2817 A sequence of numbers（快速幂取模） #

> **原题链接：**[http://acm.hdu.edu.cn/showproblem.php?pid=2817][http_acm.hdu.edu.cn_showproblem.php_pid_2817]

*  **题意：** 给出前三个数，判断是等差还是等比数列，再输入一个 k ，来计算该数列第 k 个数的值。
 *  **思路：** 先判断是等差数列还是等比数列，若是等差数列则直接计算，若是等比数列，则用快速幂取模计算。

**Code（Java）：**

import java.util.Scanner;
    import java.math.*;
    public class Main { 
        static long q_pow(long a, long n, long mod) { 
            long ans=1, base=a;
            while(n!=0) { 
                if((n&1)!=0)    ans=ans*base%mod;
                base=base*base%mod;
                n>>=1;
            }
            return ans;
        }
        public static void main(String[] args) { 
            Scanner cin = new Scanner(System.in);
            int t = cin.nextInt();
            while(t-- >0) { 
                long a = cin.nextLong();
                long b = cin.nextLong();
                long c = cin.nextLong();
                long k = cin.nextLong();
                if(b-a==c-b) { 
                    long d = b-a;
                    long ans = a+(k-1)*d%200907;
                    System.out.println(ans%200907);
                }else { 
                    long q = b/a;
                    long ans = a*q_pow(q,k-1,200907)%200907;
                    System.out.println(ans);
                }
            }
        }
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1061]: http://acm.hdu.edu.cn/showproblem.php?pid=1061
[http_acm.hdu.edu.cn_showproblem.php_pid_2817]: http://acm.hdu.edu.cn/showproblem.php?pid=2817