数论

快速幂

Posted by Liao on 2019-09-02

快速幂模板

1
2
3
4
5
6
7
8
9
10
11
12
13
long long fastpow(long long x,long long n)
{
    int base = x;
    int res = 1;
    while(n)
    {
        if(n&1)
            res = (res%mod * base%mod)%mod;
        base = (base%mod * base%mod)%mod;
        n>>=1;
    }
     return res;
}

HDU A sequence of numbers

输入前三个数字，判断这个是等差还是等比数列，求第k个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;
const long long mod = 200907;
long long fastpow(long long x,long long n)
{
    int base = x;
    int res = 1;
    while(n)
    {
        if(n&1)
            res = (res%mod * base%mod)%mod;
        base = (base%mod * base%mod)%mod;
        n>>=1;
    }
     return res;
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        long long a1,a2,a3,k;
        long long ans,d,q;
        cin >> a1 >> a2 >> a3 >>k;
        if(a3-a2 == a2-a1)  //等差数列
        {
            d = a3-a2;
            ans = (a1%mod+((k-1)*d)%mod)%mod; //an = a1 + (n-1)*d
        }
        else  //等比数列
        {
            q = (a2/a1)%mod;
            ans = ((a1)%mod*(fastpow(q,k-1))%mod)%mod;  //an = a1*q^(n-1)
        }
        cout << ans <<endl;
    }
    return 0;
}

FEATURED TAGS
数论
FRIENDS