PTK C++

#include <bits/stdc++.h>
using namespace std;

int f[1000005];
int n,m,k;
int d[1000001];
void nhap()
{
    scanf("%d%d%d",&n,&m,&k);
}

void taomang()
{
    f[1]=1;f[2]=1;
    for (int i=3;i<=n;i++) 
    	f[i]=(f[i-1]+f[i-2])%m;
}

void qs(int l,int r)
{
    int i,j,x,t;
    x=f[(l+r)/2];
    i=l;j=r;
    while (i<=j)
    {
        while (f[i]<x) i++;
        while (f[j]>x) j--;
        if (i<=j)
        {
            t=f[i];
            f[i]=f[j];
            f[j]=t;
            i++;j--;
        }
    }
    if (l<j) qs(l,j);
    if (i<r) qs(i,r);
}

void taod()
{
    int x=1,y=1,z;
    for (int i=3;i<=n;i++)
    {
        z=(x+y)%m;
        d[z]++;
        y=x;
        x=z;
    }
}

void giai()
{
    int res=0,i=-1;
    while (res<k)
    {
        i++;
        res+=d[i];
        if (res>k)
        {
            printf("%d",i);
            return;
        }
        //i++;
    }
    printf("%d",i-1);
}

void xuli()
{
    if (n<=1000000)
    {
        taomang();
        qs(1,n);
        printf("%d",f[k]);
    }
    else
    {
        taod();
        giai();
    }
}

int main()
{
   // freopen("ptk.inp","r",stdin);
   // freopen("ptk.out","w",stdout);
    nhap();
    xuli();
}