Problem Description
The so-called best problem solver can easily solve this problem, with his/her childhood sweetheart.
It is known that
y=(5+26√)1+2x.
For a given integer
x (0≤x<232) and a given prime number
M (M≤46337), print
[y]%M. (
[y] means the integer part of
y)
Input
T (1<T≤1000), indicating there are
T test cases.
Following are
T lines, each containing two integers
x and
M, as introduced above.
Output
T lines.
Each line contains an integer representing
[y]%M.
Sample Input
7
0 46337
1 46337
3 46337
1 46337
21 46337
321 46337
4321 46337
Sample Output
Case #1: 97
Case #2: 969
Case #3: 16537
Case #4: 969
Case #5: 40453
Case #6: 10211
Case #7: 17947
矩阵乘法+循环节判断
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
typedef long long LL;
int T,t=0,m,f[50000];
unsigned int n;
struct martix
{
unsigned int a[2][2];
martix(){memset(a,0,sizeof(a));}
martix operator*(const martix &b)
{
martix c;
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
for (int k=0;k<2;k++)
(c.a[i][k]+=a[i][j]*b.a[j][k])%=m;
return c;
}
};
bool operator!=(const martix &a,const martix &b)
{
if (a.a[0][0]!=b.a[0][0]) return true;
if (a.a[0][1]!=b.a[0][1]) return true;
if (a.a[1][0]!=b.a[1][0]) return true;
return false;
}
int get(unsigned int n,int m)
{
int ans=1;
for (int i=2;n;n>>=1)
{
if (n&1) (ans*=i)%=m;
i=(i*i)%m;
}
return (ans+1)%m;
}
martix mget(martix a,int x)
{
martix c=a;
if (x<=0) return c;
for (x-=1;x;x>>=1)
{
if (x&1) c=c*a;
a=a*a;
}
return c;
}
int query()
{
if (f[m]) return f[m];
martix b,c;
int loop=1;
b.a[0][0]=10%m;
b.a[0][1]=1%m;
b.a[1][0]=(m-1)%m;
c=b*b;
while (b!=c) {c=c*b; loop++; }
f[m]=loop;
return loop;
}
int main()
{
memset(f,0,sizeof(f));
scanf("%d",&T);
while (T--)
{
scanf("%u%d",&n,&m);
martix a,b,c;
int loop=1;
a.a[0][0]=98%m;
a.a[0][1]=10%m;
b.a[0][0]=10%m;
b.a[0][1]=1%m;
b.a[1][0]=(m-1)%m;
n=get(n,query());
c=mget(b,n-1);
a=a*c;
printf("Case #%d: %d\n",++t,(a.a[0][1]+m-1)%m);
}
return 0;
}