hdu 4794 Arnold (二次剩余，斐波那契循环节)
题意：
给定一个 N∗N(N≤4e9) 的矩阵，现在经过这样一个变换：将 (x,y) 变为 ((x+y)%N,(x+2×y)%N)(0≤x<N,0≤y<N) 现在求经过多少次这样的变换之后在回到 N∗N 的原始矩阵。
思路：
在模n的剩余系下可以写成(fib(n)x+fib(n+1)y,fib(n+1)x+fib(n+2)y)的形式fib(n)表示Fibonacci数列的第n项
所以就成了斐波那契数列循环节。。经典题。注意会爆long long,要用ULL
又写了遍板子，去年的东西都忘得差不多了orz
1/* ***********************************************
2Author :111qqz
3File Name :code/hdu/4794.cpp
4************************************************ */
5
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef unsigned long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26
27using namespace std;
28const double eps = 1E-8;
29const int dx4[4]={1,0,0,-1};
30const int dy4[4]={0,-1,1,0};
31const int inf = 0x3f3f3f3f;
32struct Mat
33{
34 LL mat[2][2];
35 void clear()
36 {
37 ms(mat,0);
38 }
39 void pr()
40 {
41 for ( int i = 0 ; i < 2 ; i++)
42 for ( int j = 0 ; j < 2 ; j++)
43 printf("%lld%c",mat[i][j],j==1?'\n':' ');
44 }
45}M,M1;
46const Mat P = {1,1,1,0};
47Mat mul (Mat a,Mat b,LL mod)
48{
49 Mat c;
50 c.clear();
51 for ( int i = 0 ; i < 2 ; i++)
52 for ( int j = 0 ; j < 2 ; j++)
53 for ( int k = 0 ; k < 2 ; k++)
54 c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]%mod)%mod;
55 return c;
56}
57Mat mat_ksm(Mat a,LL b,LL mod)
58{
59 Mat res;
60 res.clear();
61 for ( int i = 0 ; i < 2 ; i++) res.mat[i][i] = 1;
62 while (b>0)
63 {
64 if (b&1) res = mul(res,a,mod);
65 b = b >> 1LL;
66 a = mul(a,a,mod);
67 }
68 return res;
69}
70LL gcd(LL a,LL b)
71{
72 return b?gcd(b,a%b):a;
73}
74const int N = 5E6+7;
75bool prime[N];
76int p[N];
77int pri_tot;
78void Lineisprime() //换成线性晒了。
79{
80 // int cnt = 0 ;
81 ms(prime,true);
82 for ( int i = 2 ; i < N ; i++)
83 {
84 if (prime[i]) p[pri_tot++] = i ;
85 for ( int j = 1 ; j < pri_tot && i*p[j] < N ; j++)
86 {
87 prime[i*p[j]] = false;
88 if (i%p[j]==0) break;
89 }
90 }
91}
92
93LL ksm( LL a,LL b,LL mod)
94{
95 LL res = 1;
96 while (b>0)
97 {
98 if (b&1) res = (res * a) % mod;
99 b = b >> 1LL;
100 a = a * a % mod;
101 }
102 return res;
103}
104LL legendre(LL a,LL p) //勒让德符号,判断二次剩余
105{
106 if (ksm(a,(p-1)>>1,p)==1) return 1;
107 return -1;
108}
109
110LL pri[N],num[N];//分解质因数的底数和指数。
111int cnt; //质因子的个数
112void solve(LL n,LL *pri,LL *num)
113{
114 cnt = 0 ;
115 for ( int i = 0 ; 1LL*p[i] * p[i] <= n && i < pri_tot ; i++)
116 {
117 if (n%p[i]==0)
118 {
119 int Num = 0 ;
120 pri[cnt] = p[i];
121 while (n%p[i]==0)
122 {
123 Num++;
124 n/=p[i];
125 }
126 num[cnt] = Num;
127 cnt++;
128 }
129 }
130 if (n>1)
131 {
132 pri[cnt] = n;
133 num[cnt] = 1;
134 cnt++;
135 }
136}
137LL fac[N];
138int cnt2; //n的因子的个数
139void get_fac(LL n)//得到n的所有因子
140{
141 cnt2 = 0 ;
142 for (int i = 1 ; i*i <= n ; i++)
143 {
144 if (n%i==0)
145 {
146 if (i*i!=n)
147 {
148 fac[cnt2++] = i ;
149 fac[cnt2++] = n/i;
150 }
151 else fac[cnt2++] = i;
152 }
153 }
154}
155LL delta;
156const LL LOOP[10]={3,8,20};
157LL ask_loop(int id) //我好傻啊。。并不一定所有因子都有啊。。。
158{
159 return LOOP[id];
160}
161LL find_loop(LL n)
162{
163 //cout<<"n:"<<n<<endl;
164 solve(n,pri,num);
165 //puts("pri:");
166 // for ( int i = 0 ; i < cnt ; i++) printf("i:%d %lld\n",i,pri[i]);
167 LL ans = 1;
168 //cout<<"CNT:"<<cnt<<endl;
169 for ( int i = 0 ; i < cnt ; i++)
170 {
171 LL rec = 1;
172 if (pri[i]==2) rec = 3;
173 else if (pri[i]==3) rec = 8;
174 else if (pri[i]==5) rec = 20;
175 else
176 {
177 if (legendre(5,pri[i])==1)
178 get_fac(pri[i]-1);
179 else get_fac((pri[i]+1LL)*(3-1)); //为什么可以假设循环节不大于2*(p+1)???
180 sort(fac,fac+cnt2);
181 // for ( int qqq = 0; qqq < cnt2 ; qqq++) printf("fac: %lld ",fac[qqq]);
182 for ( int j = 0 ; j < cnt2 ; j++) //挨个验证因子
183 {
184 Mat tmp = mat_ksm(M,fac[j],pri[i]); //下标从0开始，验证fac[j]为循环节，应该看fib[0]==fib[fac[j]]和fib[1]==fib[fac[j]+1]是否成立
185 tmp = mul(tmp,M1,pri[i]);
186 if (tmp.mat[0][0]==1&&tmp.mat[1][0]==0)
187 {
188 rec = fac[j];
189 break;
190 }
191 }
192
193 }
194 for ( LL j = 1 ; j < num[i] ; j++)
195 rec *=pri[i];
196 ans = ans / gcd(ans,rec) * rec;
197 }
198 return ans;
199}
200void init()
201{
202 M.clear();
203 M.mat[0][0] = M.mat[0][1] = M.mat[1][0] = 1;
204 M1.clear();
205 M1.mat[0][0] = 1;
206}
207LL n;
208int main()
209{
210
211
212 init();
213 Lineisprime();
214 while (~scanf("%llu",&n))
215 {
216 // cout<<"n:"<<n<<endl
217 if (n==2) puts("3");
218 else
219 printf("%llu\n",find_loop(n)/2);
220
221 }
222
223#ifndef ONLINE_JUDGE
224 fclose(stdin);
225#endif
226 return 0;
227}