相关连接
题目传送门：http://oi.cyo.ng/wp-content/uploads/2016/10/2016.10.19.pdf
官方题解：http://oi.cyo.ng/wp-content/uploads/2016/10/Fibonacci.pdf
解题报告
这个题目啊！有一个神奇的结论：\({F_i}|{F_j} \Rightarrow i|j\)
现在让我们来证明这个结论：
不难发现我们只需要证明：\({F_i}|{F_{i \cdot k}}\)
然后有一个明显的结论：fibonacci的通项公式在模意义下仍然适用
于是我们可以将整个数列%上\(F_i\)就可以证明啦！
当然还有一个奇怪的结论：\(\gcd ({f_i},{f_j}) = {f_{\gcd (i,j)}}\)
据说这货证明和上面的类似？
所以说这个题目线筛一下约数个数和约数的平方和就好辣！
另外，我的线筛姿势比较奇怪，不要学我啊！
相关拓展
$Fibonacci$数列还有很多妙妙的性质，以下列举一点：
- $gcd(f_n,f_m)=f_{gcd(n,m)}$
- ${f_n}^2+{f_{n-1}}^2 = f{2n+2}$
- $f_n \cdot (f_{n-1}+f_{n+1}) = f{2n+1}$
- 如果$f_k$能被$x$整除，则$f_{ki}$都可以被$x$整除
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 10000000+9;
const int MX = 10000000;
const int MOD = 1000000007;
int f1[N],f2[N],n,A,B,C,W,vout1,vout2;
int tot,pri[N],top[N],REV[50];
short vis[N],MN[N];
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;
}
inline int pow(int w, int t) {
int ret = 1;
while (t) {
if (t & 1) ret = (LL)ret * w % MOD;
w = (LL)w * w % MOD; t>>= 1;
}
return ret;
}
inline void prework(){
REV[0] = 1;
for (int i=1;i<=30;i++) {
REV[i] = pow(i,MOD-2);
}
f1[1] = 1; f2[1] = 1;
for (int i=2;i<=MX;i++) {
if (!vis[i]) {
pri[++tot] = i;
f1[i] = 2;
f2[i] = (1 + (LL)i * i) % MOD;
MN[i] = 1; top[i] = (LL)i * i % MOD;
}
for (int j=1,to,sqr;j<=tot&&i*pri[j]<=MX;j++) {
vis[to = i*pri[j]] = 1;
sqr = (LL)pri[j] * pri[j] % MOD;
if (i % pri[j]) {
f1[to] = f1[i] * 2 % MOD;
f2[to] = f2[i] * (1LL + sqr) % MOD;
MN[to] = 1;
top[to] = (LL)f2[i] * sqr % MOD;
} else {
MN[to] = MN[i] + 1;
top[to] = (LL)top[i] * sqr % MOD;
f1[to] = (f1[i] + (LL)f1[i]*REV[MN[i]+1]) % MOD;
f2[to] = (f2[i] + top[to]) % MOD;
break;
}
}
}
for (int i=3;i<=MX;i++) {
if (i % 2) {
f1[i] += 1;
f2[i] += 4;
}
}
}
int main(){
freopen("fibonacci.in","r",stdin);
freopen("fibonacci.out","w",stdout);
n = read(); W = read();
A = read(); B = read(); C = read();
prework();
for (int i=1;i<=n;i++,W=((LL)W*A+B)%C+1) {
vout1 += f1[W]; vout2 += f2[W];
vout1 %= MOD; vout2 %= MOD;
}
printf("%d %d\n",vout1,vout2);
return 0;
}
If some one wants to be updated with most recent technologies then he
must be visit this site and be up to date all the time.
Hello just wanted to give you a quick heads up. The words in your article seem to
be running off the screen in Chrome. I’m not sure
if this is a format issue or something to do with web browser
compatibility but I figured I’d post to let you know.
The design look great though! Hope you get the issue fixed soon. Kudos
Why users still make use of to read news papers when in this technological
globe everything is available on web?
I think that what you published made a lot of sense. However, what about this?
what if you added a little information? I am not suggesting your information is not good., but suppose you added a title to possibly get folk’s
attention? I mean 【日常小测】Fibonacci
– Qizy's Database is kinda plain. You could look at Yahoo’s front page and
note how they create post headlines to grab viewers interested.
You might add a video or a pic or two to get readers excited about what you’ve
written. Just my opinion, it would make your blog a little bit
more interesting.
My brother suggested I would possibly like this
web site. He was entirely right. This post actually made my day.
You can not imagine just how much time I had spent for
this info! Thanks!
I think this is among the most vital info for me.
And i am glad reading your article. But want to remark on some general things, The
site style is perfect, the articles is really
excellent : D. Good job, cheers
Fantastic beat ! I would like to apprentice even as
you amend your site, how can i subscribe for a blog website?
The account aided me a appropriate deal. I have been tiny bit familiar of this your broadcast offered vivid transparent idea
Admiring the time and energy you put into your site and in depth information you provide.
It’s good to come across a blog every once in a while that isn’t the
same old rehashed material. Wonderful read! I’ve saved your site and
I’m adding your RSS feeds to my Google account.
Outstanding story there. What occurred after? Good luck!
I’m extremely inspired together with your writing
abilities and also with the structure on your weblog.
Is that this a paid subject matter or did you customize it your self?
Either way keep up the nice quality writing, it’s uncommon to peer
a great weblog like this one today..
Everything is very open with a really clear explanation of the issues.
It was definitely informative. Your website is useful.
Thanks for sharing!
Woah! I’m really digging the template/theme of this site.
It’s simple, yet effective. A lot of times it’s difficult to
get that “perfect balance” between usability and visual appearance.
I must say you have done a fantastic job with this. Additionally, the blog loads very fast for me on Chrome.
Excellent Blog!
You are so awesome! I don’t suppose I’ve read a single thing like this before.
So great to discover another person with some unique thoughts on this issue.
Really.. thanks for starting this up. This site is something that is required on the internet, someone with a little originality!
I just could not leave your site before suggesting that I actually enjoyed the standard info a person supply to your visitors? Is gonna be again continuously in order to check up on new posts.
Hmm is anyone else encountering problems with the
pictures on this blog loading? I’m trying to find out if its
a problem on my end or if it’s the blog. Any responses would be greatly
appreciated.
Hi, i believe that i saw you visited my site so i got here to
go back the prefer?.I am attempting to in finding things to improve my site!I guess its adequate to make use of some of your concepts!!
Hi, I do think this is a great web site. I stumbledupon it 😉 I
am going to revisit once again since i have bookmarked it.
Money and freedom is the best way to change, may you be rich and
continue to help others.
Today, I went to the beachfront with my kids. I found a sea shell and
gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed.
There was a hermit crab inside and it pinched her ear. She never wants to go back!
LoL I know this is completely off topic but I had to tell someone!
Great beat ! I wish to apprentice while you amend your website, how
could i subscribe for a blog site? The account helped me a acceptable deal.
I had been a little bit acquainted of this your broadcast provided bright clear concept
Do you have any video of that? I’d like to find out more details.
Why people still make use of to read news papers when in this technological globe everything is accessible on web?
I like what you guys are up too. This type of clever work and reporting!
Keep up the very good works guys I’ve you guys to blogroll.
Nice answers in return of this issue with solid arguments
and telling the whole thing regarding that.
Hi there to all, the contents existing at this site are
truly awesome for people experience, well, keep up the
nice work fellows.
This is a great tip especially to those
fresh to the blogosphere. Simple but very accurate information… Many thanks for sharing this one.
A must read post!
Great site you have here but I was curious about if you knew of any user discussion forums that cover the same topics discussed here? I’d really love to be a part of community where I can get responses from other knowledgeable people that share the same interest. If you have any suggestions, please let me know. Bless you!