Performance Optimization

What optimizations can be done so that this code runs much faster for the following input? This version takes > 20s, about 26s on my machine.

1
18 1999999871

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
#include<iostream>

using namespace std;

int main()
{
    int t,c,p,temp,x,y,ct,flag;
    cin>>t;
    int result;
    for(int i=0; i<t; i++){
        cin>>c>>p;
        flag = 0;
        ct=-1;
        x=0;
        y=1;
        while(++ct < p-1){
                temp = x+y;
                if(ct && !x && y == 1 && temp == 1)
                        break;
                if (x == c){
                        flag = 1;
                        result = ct;
                        break;
                }
                x = y;
                y = temp%p;
        }
        if(!flag) result = -1;
    }
    cout<<result<<endl;
    return 0;
}
Last edited on
What is it and what should it do?
Its from codechef.com, I'm eager to learn different approaches. I came up with this after a lot of tries but still the performance is slow.

It is required to find the minimum n such that Fn % p = c.
Fn is the nth fibonacci term, ct is n in this code.
Range of c, 0 ≤ c ≤ p-1
p is a prime number <2000000000 and also p % 10 is guaranteed to be a perfect square. Can this property be used in any way to optimize instead of just brute-forcing?
Last edited on
Thanks.
I observed the results of mod p on Fibonacci series and noticed that they repeat themselves after a certain count (the count most of the times being p-1) and so wrote this code but it still isn't optimal, for the prime 1999999871 it loops until 1999999870.
Does p%10 being a perfect square help??
1) you are doing it all wrong.
From equation Fn % p = c → Fn = x·p + c where x ∈ N

From numbers less than p you need to check only c itself. Next one will be p+c, then 2·p+c etc.
You might want for each t = x·p + c to check if it is a fibonacci number using known formulas, calculate n of said number using other formulas and output that number.
Thanks, I will try that.
Topic archived. No new replies allowed.