#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef long long LL;
const int M=2;
struct Matrix{
LL m[M][M];
};
Matrix per= {1,0,0,1};
Matrix multi(Matrix a,Matrix b,LL MOD){
Matrix c;
int i,j,k;
for(i=0; i<M; i++){
for(j=0; j<M; j++){
c.m[i][j]=0;
for(k=0; k<M; k++){
c.m[i][j]+=a.m[i][k]*b.m[k][j]%MOD;
}
c.m[i][j]%=MOD;
}
}
return c;
}
Matrix power(Matrix a,LL k,LL MOD){
Matrix ans=per,p=a;
while(k){
if(k&1){
ans=multi(ans,p,MOD);
k--;
}
k>>=1;
p=multi(p,p,MOD);
}
return ans;
}
LL gcd(LL a,LL b){
return b? gcd(b,a%b):a;
}
LL quick_mod(LL a,LL b,LL m){
LL ans=1;
a%=m;
while(b){
if(b&1){
ans=ans*a%m;
b--;
}
b>>=1;
a=a*a%m;
}
return ans;
}
int legendre(int a,int p){
if(quick_mod(a,(p-1)>>1,p)==1) return 1;
else return -1;
}
const int N=1000005;
const int NN=50005;
bool prime[N];
int p[N];
int num[NN],pri[NN],num1[NN],pri1[NN];
int arr[NN],loop[N],k,cnt,c;
void isprime(){
k=0;
int i,j;
memset(prime,true,sizeof(prime));
for(i=2; i<N; i++){
if(prime[i]){
p[k++]=i;
for(j=i+i; j<N; j+=i){
prime[j]=false;
}
}
}
}
void find(int n,int pri[],int num[]){
cnt=0;
int t=(int)sqrt(1.0*n);
for(int i=0; p[i]<=t; i++){
if(n%p[i]==0){
int a=0;
pri[cnt]=p[i];
while(n%p[i]==0){
a++;
n/=p[i];
}
num[cnt]=a;
cnt++;
}
}
if(n>1){
pri[cnt]=n;
num[cnt]=1;
cnt++;
}
}
void dfs(int dept,int product=1){
if(dept==cnt){
arr[c++]=product;
return;
}
for(int i=0; i<=num1[dept]; i++){
dfs(dept+1,product);
product*=pri1[dept];
}
}
int find_loop(int n){
find(n,pri,num);
int cnt1=cnt;
LL ans=1;
for(int i=0; i<cnt1; i++){
c=0;
int record=1;
if(pri[i]==2)
record=3;
else if(pri[i]==3)
record=8;
else if(pri[i]==5)
record=20;
else{
if(legendre(5,pri[i])==1)
find(pri[i]-1,pri1,num1);
else
find(2*(pri[i]+1),pri1,num1);
dfs(0,1);
sort(arr,arr+c);
for(int k=0; k<c; k++){
Matrix A;
A.m[0][0]=1;
A.m[0][1]=1;
A.m[1][0]=1;
A.m[1][1]=0;
Matrix a=power(A,arr[k]-1,pri[i]);
int x=(a.m[0][0]+a.m[0][1])%pri[i];
int y=(a.m[1][0]+a.m[1][1])%pri[i];
if(x==1&&y==0){
record=arr[k];
break;
}
}
}
for(int k=1; k<num[i]; k++)
record*=pri[i];
ans=ans/gcd(ans,record)*record;
}
return ans;
}
void Solve(int p,int k){
loop[0]=p;
for(int i=1; i<=k; i++)
loop[i]=find_loop(loop[i-1]);
}
int work(int n,int k,int p){
int t=n;
LL ret,MOD;
Matrix ans;
Matrix A;
A.m[0][0]=1;
A.m[0][1]=1;
A.m[1][0]=1;
A.m[1][1]=0;
Solve(p,k);
for(int i=k; i>=0; i--){
MOD=loop[i];
ans=power(A,t,MOD);
ret=(ans.m[1][0]+ans.m[1][1])%MOD;
t=ret;
}
return ret;
}
int main(){
isprime();
int T,n,k,p,tt=1;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&k,&p);
printf("Case #%d: %d\n",tt++,work(n,k,p));
}
return 0;
}
HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu.
版权申诉
149 浏览量
2022-09-23
04:12:00
上传
评论
收藏 153KB RAR 举报
HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu. （411个子文件） 
3978a.cpp 4KB 6034.cpp 3KB 1107.cpp 3KB 1430a.cpp 3KB 1540.cpp 3KB 1983.cpp 2KB 3978.cpp 2KB 6376.cpp 2KB 3308.cpp 2KB 4417.cpp 2KB 3977.cpp 2KB 1255.cpp 2KB 2665.cpp 2KB 2874.cpp 2KB 4884.cpp 2KB 6376a.cpp 2KB 1428.cpp 2KB 1533.cpp 2KB 1565.cpp 2KB 4292.cpp 2KB 1105.cpp 2KB 1314.cpp 2KB 5818.cpp 2KB 4909.cpp 1KB 4885.cpp 1KB 3948.cpp 1KB 4001.cpp 1KB 2767.cpp 1KB 3652.cpp 1KB 1756.cpp 1KB 4932.cpp 1KB 4725.cpp 1KB 6444.cpp 1KB 1254.cpp 1KB 1225.cpp 1KB 1543.cpp 1KB 1311.cpp 1KB 4920.cpp 1KB 1429.cpp 1KB 1432a.cpp 1KB 4002.cpp 1KB 1430.cpp 1KB 4720.cpp 1KB 1245.cpp 1KB 4328.cpp 1KB 6375.cpp 1KB 2723.cpp 1KB 2255.cpp 1KB 1348.cpp 1KB 1308.cpp 1KB 5674.cpp 1KB 1277.cpp 1KB 1413.cpp 1KB 2607.cpp 1KB 3045.cpp 1KB 5950.cpp 1KB 1415.cpp 1KB 6113.cpp 1KB 1223.cpp 1024B 1512.cpp 1021B 1252.cpp 1014B 1503.cpp 992B 1224.cpp 985B 1757.cpp 985B 3001.cpp 957B 1317.cpp 951B 1432.cpp 951B 1536.cpp 943B 1384.cpp 940B 6299.cpp 934B 1307.cpp 929B 1350.cpp 923B 1427.cpp 921B 6410.cpp 920B 1455.cpp 915B 1261.cpp 915B 6109.cpp 904B 1822.cpp 900B 1502.cpp 897B 1583.cpp 893B 4500.cpp 890B 4054.cpp 882B 1221.cpp 876B 6447.cpp 870B 1930.cpp 866B 2852.cpp 860B 5547.cpp 850B 1598.cpp 847B 4565.cpp 839B 2213.cpp 839B 2952.cpp 838B 2671.cpp 833B 1355.cpp 832B 6446.cpp 831B 1318.cpp 829B 1524.cpp 828B 4463.cpp 811B 1296.cpp 806B 3823.cpp 800B 2845.cpp 798B共 411 条
- 1
- 2
- 3
- 4
- 5
资源评论
