欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Uva 11582 Colossal Fibonacci Numbers! (循环节、幂取模、打表)

程序员文章站 2022-07-14 10:00:52
...

The i’th Fibonacci number f(i) is recursively defined in the following way:
f(0)=0 and f(1)=1
f(i+2)=f(i+1)+f(i)for every i0
Uva 11582 Colossal Fibonacci Numbers! (循环节、幂取模、打表)
Your task is to compute some values of this sequence.
Input
Input begins with an integer t10,000, the number of test cases.
Each test case consists of three integers a, b, n where 0a,b<264
(a and b will not both be zero) and 1n1000.
Output
For each test case, output a single line containing the remainder of f(ab) upon division by n
Sample Input
3
1 1 2
2 3 1000
18446744073709551615 18446744073709551615 1000
Sample Output
1
21
250
ps: 这题数据非常大,必须通过找循环节来解决,f(i+2)=f(i+1)+f(i),当f(i), f(i+1)与前面的数相同时,就会开始产生循环节。因为余数最多n种,所以最多n2项就会出现重复。鉴于数据规模实在过于庞大(106103=109),单纯靠每次找循环节和快速幂会造成TLE(我上交tle了(,,•́ . •̀,,) ), 所以还需要将1~1000取模的所有情况打表,就是记录他们的循环节。
TLE code:

#include<iostream>
using namespace std;
const int maxn = 1e6+10;
int fib[maxn];
int pow(unsigned long long a, unsigned long long b, int c)
{//幂取模 a^b % c
    int ans = 1;
    a = a % c;
    while(b > 0)
    {
        if(b & 1) ans = ((a % c) * (ans % c)) % c;
        a = (a * a) % c;
        b = b >> 1;
    }
    return ans;
}
int main()
{
    //虽然双加速但也超时
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    unsigned long long a, b;
    int c;
    while(n--)
    {
        cin>>a>>b>>c;
        int maxt = c * c + 4;
        fib[0] = 0 , fib[1] = 1;
        for(int i = 2; i < maxt; i++)fib[i] = (fib[i - 1] % c + fib[i - 2] % c) % c;
        int temp = 1;
        for(int i = 2; i < maxt; i++){
            if(fib[0] == fib[i] && fib[1] == fib[i+1])
            {
                temp = i;
                break;
            }
        }
        int tt = pow(a, b, temp);
        if(a == 0 || c == 1)cout<<0<<endl;
        else cout<<fib[tt % temp]<<endl;
    }
    return 0;
}

改好后:

#include<iostream>
#include<vector>
using namespace std;
vector<int> fib[1004];//保存循环节
void init()
{//打表保存循环节
    for(int i = 2; i <= 1000; i++)
    {
        int mod = i;
        int a = 0, b = 1;
        int c = (a + b) % mod;
        fib[i].push_back(a);
        fib[i].push_back(b);
        fib[i].push_back(c);
        while(!(b == 0 && c == 1))
        {
            a = b;
            b = c;
            c = ((a % mod) + (b % mod)) % mod;
            fib[i].push_back(c);
        }
        fib[i].pop_back();
        fib[i].pop_back();
    }
}
int pow(unsigned long long a, unsigned long long b, int n)
{//幂取模
    int ans = 1;
    while(b > 0)
    {
        if(b & 1)ans = ((a % n) * (ans % n)) % n;
        a = ((a % n) * (a % n)) % n;
        b = b >> 1;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    init();
    while(T--)
    {
        unsigned long long a, b;
        int n;
        cin>>a>>b>>n;
        if(a == 0 || n == 0){//f(0) = 0
            cout<<0<<endl;
            continue;
        }
        int t = pow(a, b, fib[n].size());
        cout<<fib[n][t]<<endl;
    }
    return 0;
}
相关标签: 循环节 幂取模