poj1845 逆元（费马小定理）/ 递归二分求等比数列 + 快速幂 + 素因子分解

/*
Time:2019.12.9
Author: Goven
type：逆元（费马小定理）/ 递归二分求等比数列 + 快速幂 + 素因子分解
测试数据；http://poj.org/showmessage?message_id=106214
*/

法1：快速幂 + 费马小定理

/*
type:快速幂 + 费马小定理 
ref:https://blog.csdn.net/qq_42680294/article/details/100943261
注：
1.快速幂 指数参数为ll（传参时也要显示转换）
2.快速幂 底数要先模mod(否则第一次 a = a * a % mod会溢出)
3.取余运算时如果有减法，一定要+mod保证>0 
*/
#include<iostream>
#include<cmath>
#define MAXA 50000005
#define mod 9901
using namespace std;
typedef long long ll;

int a, b, res;

int quick_pow(int a, ll b) {//快速幂  att:b的类型为 ll ,因为传入参数的时候b不能取余 
    a = a % mod;//err2:这里如果不模的话，第一次 a = a * a % mod; 就会出问题 
    int res = 1;
    while(b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }   
    return res;
}

int inv(int a) {//费马小定理求逆元 
    return quick_pow(a, mod - 2);   
}

void fun(int i, int k) {//求一个等比数列的和取模 
    if ((i - 1) % mod == 0) {//逆元不存在 
        res = ((ll)b * k + 1) % mod * res % mod;//err1:ll没有加 
    }
    else{
        int tp1 = (quick_pow(i, (ll)b * k + 1) - 1 + mod) % mod;//err1:ll没有加 //err3: 一开始写的是tp1 = quick_pow(i, (ll)b * k + 1) - 1，可能结果是-1 
        int tp2 = inv(i - 1);
        res = res * tp1 % mod * tp2 % mod;
    }
}

int main()
{
    
    cin >> a >> b;
    res = 1;
    int n = sqrt(1.0 * a);
    for (int i = 2; i <= n; i++) {//att1:结束条件不能是a > 1 
        if (a % i == 0) {
            int k = 0;
            while (a % i == 0) {
                k++;
                a /= i;
            }
            fun(i, k);
        } 
    } 
    if (a > 1) fun(a, 1);//att2:不要漏了 
    cout << res << endl;
    return 0;
}

法2：快速幂(快速乘法) + 变换模值求分数取模

/*
type:快速幂(快速乘法) + 变换模值 
ref: 
https://blog.csdn.net/qingshui23/article/details/52154321
https://blog.csdn.net/a601025382s/article/details/12233213
*/
#include<iostream>
#include<cmath>
#define MAXA 50000005
#define mod 9901
using namespace std;
typedef long long ll;

int a, b, res;

ll mul(ll a, ll b, ll m) {//大数乘法 
    ll res = 0;
    while(b) {
        if (b & 1) res = (res + a) % m;
        a = a * 2 % m;
        b >>= 1;
    }
    return res;
}

ll quick_pow(ll a, ll b, ll m) {//快速幂 
    a = a % m;//att1:这里如果不模的话，第一次 a = a * a % mod; 就会出问题  
    ll res = 1;
    while(b) {
        if (b & 1) {
            res = mul(res, a, m);
        }
        a = mul(a, a, m);
        b >>= 1;
    }   
    return res;
}

void fun(int i, int k) {//求一个等比数列的和取模 --变换模值 
    ll m = (ll)mod * (i - 1);
    ll tp = quick_pow(i, (ll)b * k + 1, m) - 1;
    tp = (tp + m) % m;//att2:可能小于0 
    tp = tp / (i - 1);
    res = res * tp % mod;   
}

int main()
{
    
    cin >> a >> b;
    res = 1;
    int n = sqrt(1.0 * a);
    for (int i = 2; i <= n; i++) {//att3:结束条件不能是a > 1 
        if (a % i == 0) {
            int k = 0;
            while (a % i == 0) {
                k++;
                a /= i;
            }
            fun(i, k);
        } 
    } 
    if (a > 1) fun(a, 1);//att4:不要漏了 
    cout << res << endl;
    return 0;
}

法3：快速幂 + 递归二分法求等比数列：

/*
type:快速幂 + 递归二分法求等比数列 
ref: 
https://blog.csdn.net/weixin_30905133/article/details/94846038
https://blog.csdn.net/a601025382s/article/details/12233213
*/
#include<iostream>
#include<cmath>
#define MAXA 50000005
#define mod 9901
using namespace std;
typedef long long ll;

int quick_pow(int x, ll y) {
    x = x % mod;
    int res = 1;
    while(y) {
        if(y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }   
    return res;
}

int sum(int x, ll y) {//二分法求1 + x + ... + x^y 
    if (!y) return 1;
    if (y & 1) {
        return (1 + quick_pow(x, (ll)y/2+1)) * sum(x, (ll)y/2) % mod;
    }
    else {
        return ((1 + quick_pow(x, (ll)y/2+1)) * sum(x, (ll)y/2-1) + quick_pow(x, (ll)y/2)) % mod;
    }
}

int main()
{
    int a, b, res;
    cin >> a >> b;
    res = 1;
    int n = sqrt(1.0 * a);
    for (int i = 2; i <= n; i++) {//att1:结束条件不能是a > 1 
        if (a % i == 0) {
            int k = 0;
            while (a % i == 0) {
                k++;
                a /= i;
            }
            res = res * sum(i, (ll)k * b) % mod;
        } 
    } 
    if (a > 1) res = res * sum(a, b) % mod;//att2:不要漏了 
    cout << res << endl;
    return 0;
}