2015
09-18

Arnold

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 182    Accepted Submission(s): 33

Problem Description
Do you know Vladimir Arnold? He’s a mathematician who demonstrated an image transformation method called arnold transformation, which could shuffle all pixels in an image, and after a serials of this transformation, the image would be transformed to its original
form.
The transformation method is quite simple. For a given image with N × N pixels (Width and height are both equal to N), a pixel at location (x, y) will be shuffled to location ( (x + y) % N , (x + 2 × y) % N ) (0 ≤ x < N, 0 ≤ y < N). In one step of transformation,
all N × N pixels will be shuffled to new corresponding location, making the image a chaotic one. You can do the transformation as many times as you can.
The arnold transformation is very interesting. For every image of size N × N, after finite steps of transformation, the image will become exact the same as the original one. The minimum number of steps which make every possible image become the same as origin
will be called as period of arnold transformation. For a given N, can you calculate the period?

Input
There will be about 200 test cases. For each test case, there will be an integer N in one line. Here N (2 ≤ N ≤ 4000000000) equals to width and height of images.

Output
For each test case, please calculate the period of arnold transformation and output it in one line.

Sample Input
11
29
41

Sample Output
5
7
20

(f1,f2)->(f3,f4)->……->(fn,f1)->(f2,f3)->……->(f(n-1),fn) 所以奇数就不用除以2

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <stdio.h>
#include <cmath>
#include <math.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,b,a) for(int i = (b); i >= (a); --i)
#define clr(a,x) memset(a,(x),sizeof(a))
#define LL unsigned long long
#define eps 1e-8
using namespace std;
LL n;

LL gcd(LL a, LL b)
{
while (a && b) {
if (a > b) a %= b;
else b %= a;
}
return a + b;
}

LL lcm(LL a,LL b)
{
return a * b / gcd(a,b);
}

void mul(LL A[2][2],LL B[2][2],LL ret[2][2],LL mod)
{
LL C[2][2] = { 0 };
rep(i,0,2) rep(j,0,2) rep(k,0,2)
C[i][j] = (C[i][j] + A[i][k] * B[k][j] % mod) % mod;
rep(i,0,2) rep(j,0,2)
ret[i][j] = C[i][j];
}

void qpow(LL base[2][2],LL p,LL dest[2][2],LL mod)
{
LL ret[2][2] = { 0 };
ret[0][0] = ret[1][1] = 1;
while (p > 0) {
if (p & 1) mul(ret,base,ret,mod);
mul(base,base,base,mod);
p >>= 1;
}
rep(i,0,2) rep(j,0,2) dest[i][j] = ret[i][j];
}

LL qpow(LL base,LL p,LL mod)
{
LL ret = 1;
while (p) {
if (p & 1) ret = ret * base % mod;
base = base * base % mod;
p >>= 1;
}
return ret;
}

LL S[10000],c;
LL f1,f2;
void F(LL p,LL mod)
{
LL A[2][2] = { 0 };
A[0][0] = 1; A[0][1] = 1;
A[1][0] = 1; A[1][1] = 0;
qpow(A,p-1,A,mod);
f1 = (A[1][0]+A[1][1]) % mod; f2 = (A[0][0] + A[0][1]) % mod;
}

LL loop(LL mod)
{
if (mod == 2) return 3;
else if (mod == 3) return 8;
else if (mod == 5) return 20;
LL p;
if (qpow(5,(mod-1)>>1,mod) == 1) p = mod - 1;
else p = 2*(mod + 1);
c = 0;
for(LL i = 1; i * i <= p; ++i) if (p % i == 0) {
LL x = i , y = p / i;
F(x,mod);
if (f1 == 0 && f2 == 1) return x;
if (y != x) S[c++] = y;
}
while (c > 0) {
F(S[--c],mod);
if (f1 == 0 && f2 == 1) return S[c];
}
return 0;
}

int main()
{
// cout << qpow(5,(mod - 1)/2,mod) << endl;
#ifdef ACM
freopen("in.txt", "r", stdin);
#endif // ACM
while (cin >> n) {
LL x = n;
LL ans = 1;
for(LL i = 2; i * i <= x; ++i) if (x % i == 0) {
LL len = loop(i);
LL S = 1;
do x /= i, S = S * i;
while (x % i == 0);
S /= i; S = S * len;
ans = lcm(ans,S);
}
if (x > 1) {
LL len = loop(x);
ans = lcm(ans,len);
}
if (ans % 2 == 0) ans /= 2;
printf("%I64u\n",ans);
}
}

﻿﻿

1. 共产主义运动就是要促进全世界人民的觉醒，在此基础上建立共产主义社会，不宣传怎么团结全世界人民打碎旧世界建设新世界？