【51NOD 1195】斐波那契数列的循环节

相关链接

题目传送门:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1195
二次剩余相关:http://staff.ustc.edu.cn/~lvmin05/jssl/Chap3%20%B6%FE%B4%CE%CA%A3%D3%E0.ppt
二次剩余相关:http://pan.baidu.com/s/1geBDodH
神犇题解:http://blog.csdn.net/acdreamers/article/details/10983813

解题报告

我们分三步走:

  1. 将模数质因数分解
  2. 对于每一个$p_i^m$我们计算其循环节$l_i$
  3. 将所有$l_i$取$lcm$

显然第一步和第三步没有难度
我们考虑第二步,这里有一个神奇得结论:
若$G(p)$为Fibonacci数列在模素数$p$意义下的最短循环节
那么$\bmod p^m$的最短循环节为$G(p)\cdot p^{m-1}$

现在问题转化为求$G(p)$,这里又有一个神奇的结论:
若$5$为$p$的二次剩余,则$G(p)$为$p-1$的因子。否则为$2(p+1)$的因子
然后我们就可以通过从小到大枚举因数+$O(\log n)$判断的方法得到答案了

另外的话,这个算法似乎没有比较准确的复杂度。不过我们可以假装他是$O(\sqrt{n} \log n)$的
再另外的话,这份代码会$T$,但我又不想优化了,反正这个东西也不可能考 QwQ

Code

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

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

class Fibonacci{
	int ans[4],tra[4],MOD;
	public:
		inline bool cal(int t, int mod) {
			ans[1] = tra[1] = tra[2] = tra[3] = 1;
			ans[0] = ans[2] = ans[3] = tra[0] = 0; MOD = mod;
			Pow(tra, tra, t - 2); Mul(ans, ans, tra);
			return ans[1] == 1 && !ans[0];
		}
	private:
		inline void Pow(int *ans, int *a, int t) {
			static int ret[4],cur[4]; 
			ret[0]=ret[3]=1; ret[1]=ret[2]=0;
			memcpy(cur,a,sizeof(cur));
			for (;t;t>>=1,Mul(cur,cur,cur))
				if (t&1) Mul(ret,cur,ret);
			memcpy(ans, ret, sizeof(ret));
		}
		inline void Mul(int *ans, int *a, int *b) {
			static int ret[4];
			ret[0] = ((ll)a[0] * b[0] + (ll)a[1] * b[2]) % MOD;
			ret[1] = ((ll)a[0] * b[1] + (ll)a[1] * b[3]) % MOD;
			ret[2] = ((ll)a[2] * b[0] + (ll)a[3] * b[2]) % MOD;
			ret[3] = ((ll)a[2] * b[1] + (ll)a[3] * b[3]) % MOD;
			memcpy(ans, ret, sizeof(ret));
		}
}fib;

ll GCD(ll a, ll b) {
	return b? GCD(b, a%b): a;
}

int Pow(int w, int t, int mod) {
	int ret = 1;
	for (;t;t>>=1,w=(ll)w*w%mod)
		if (t&1) ret=(ll)ret*w%mod;
	return ret;
}

inline ll G(ll p) {
	if (p == 2) return 3;
	else if (p == 3) return 8;
	else if (p == 5) return 20;
	static ll LIM = 0; stack<int> stk;
	if (Pow(5, (p-1)/2, p) == 1) LIM = p - 1;
	else LIM = p + 1 << 1; 
	for (int i=1;i*i<=LIM;i++) {
		if (LIM % i == 0) {
			if (fib.cal(i+2, p)) return i;
			else stk.push(LIM / i);
		}
	}
	for (int ret;!stk.empty();) {
		ret = stk.top(); stk.pop();
		if (fib.cal(ret+2, p)) return ret;
	}
}

inline ll cal(int a, int b) {
	static ll INF = 4e18, ret;
	for (ret=G(a);b>1;b--) ret = ret * a;
	return ret;
}

inline ll solve(int mod) {
	static const int N = 1e5;
	static int pri[N],cnt[N],tot;
	if (mod == 1) return 1; tot = 0; 
	for (int i=2;i*i<=mod;i++) {
		if (mod % i == 0) {
			pri[++tot] = i; cnt[tot] = 0;
			for (;mod%i==0;mod/=i) ++cnt[tot];
		}
	} if (mod>1) pri[++tot] = mod, cnt[tot]=1;
	ll ret = 1;
	for (int i=1,tmp;i<=tot;i++) {
		tmp = cal(pri[i], cnt[i]);
		ret = ret / GCD(ret, tmp) * tmp;
	} return ret;
}

int main() {
	for (int T=read();T;T--) 
		printf("%lld\n",solve(read()));
	return 0;
}

27 thoughts to “【51NOD 1195】斐波那契数列的循环节”

  1. Attractive section of content. I just stumbled upon your site and
    in accession capital to assert that I get actually enjoyed account your blog posts.
    Any way I’ll be subscribing to your augment and even I achievement you access consistently quickly.

  2. Admiring the time and effort you put into your website and in depth information you offer.
    It’s good to come across a blog every once in a while
    that isn’t the same out of date rehashed material. Excellent
    read! I’ve bookmarked your site and I’m including your RSS feeds to
    my Google account.

  3. Hello all, here every one is sharing these kinds of know-how, so it’s
    pleasant to read this webpage, and I used to pay a
    visit this website everyday.

  4. Hi, I do believe this is a great blog. I stumbledupon it 😉 I may revisit yet
    again since I bookmarked it. Money and freedom is the greatest way to change, may you be rich and continue to
    guide other people.

  5. I was curious if you ever considered changing the page layout of your site?
    Its very well written; I love what youve got to say.

    But maybe you could a little more in the way
    of content so people could connect with it better.

    Youve got an awful lot of text for only having one or two images.
    Maybe you could space it out better?

  6. Have you ever thought about publishing an ebook or guest authoring on other sites?

    I have a blog based upon on the same ideas you discuss and would love to have you
    share some stories/information. I know my visitors would enjoy your work.

    If you’re even remotely interested, feel free to shoot me an e-mail.

  7. Hello! This is my 1st comment here so I just wanted to give a quick shout
    out and tell you I genuinely enjoy reading your articles.
    Can you recommend any other blogs/websites/forums that
    deal with the same subjects? Thanks for your time!

  8. We’re a group of volunteers and starting a brand new scheme in our community.
    Your web site provided us with valuable information to work on. You have performed an impressive process and our whole neighborhood will probably be thankful to you.

  9. Hi! I’ve been following your site for some time now and finally got the courage to go
    ahead and give you a shout out from Lubbock Texas! Just wanted to mention keep up the great work!

  10. I think this is among the most significant information for me.
    And i’m glad reading your article. But should remark on few general things, The web site style is wonderful,
    the articles is really nice : D. Good job, cheers

  11. When some one searches for his essential thing, therefore he/she
    desires to be available that in detail, therefore that thing is maintained over here.

  12. You’re so cool! I do not think I’ve read through anything like this before.
    So wonderful to find someone with some genuine thoughts on this
    subject matter. Seriously.. thank you for starting this up.
    This website is one thing that is needed on the internet, someone
    with some originality!

  13. My partner and I stumbled over here by a different web page and thought I
    may as well check things out. I like what I see so now i am following you.
    Look forward to looking into your web page for a second time.

  14. I’m amazed, I have to admit. Rarely do I encounter a blog that’s equally educative and amusing, and without a doubt,
    you have hit the nail on the head. The issue is an issue that not enough people are speaking intelligently about.
    I’m very happy that I came across this in my hunt for something regarding this.

  15. I am not sure where you’re getting your info, but
    good topic. I needs to spend some time learning more or understanding more.
    Thanks for wonderful information I was looking for this info for my
    mission.

  16. With havin so much written content do you ever run into any problems of plagorism or copyright violation? My blog has a lot of completely unique content I’ve either written myself or outsourced but it looks like a lot of it is popping it up all over the internet without my
    permission. Do you know any methods to help prevent content from
    being stolen? I’d really appreciate it.

  17. you’re in point of fact a good webmaster. The website loading pace
    is incredible. It sort of feels that you are doing any distinctive
    trick. In addition, The contents are masterwork. you have performed a great task
    on this matter!

  18. Great goods from you, man. I’ve understand your stuff previous to
    and you are just extremely fantastic. I really like what you’ve acquired here, certainly like what you’re saying and the
    way in which you say it. You make it entertaining and you still care for to keep it sensible.
    I can’t wait to read much more from you. This is really a terrific website.

  19. I’m amazed, I have to admit. Seldom do I encounter a blog that’s both equally educative and entertaining,
    and without a doubt, you’ve hit the nail on the head.
    The problem is an issue that too few folks are speaking intelligently about.
    Now i’m very happy that I stumbled across this in my search for
    something regarding this.

  20. Hi there, just became alert to your blog through Google, and found that it is truly informative. I am going to watch out for brussels. I’ll be grateful if you continue this in future. Numerous people will be benefited from your writing. Cheers!

Leave a Reply to tinyurl.com Cancel reply

Your email address will not be published. Required fields are marked *