A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2813 奇妙的Fibonacci
发表于: | 分类: Oi | 评论:0 | 阅读:144

Fibonacci数列是这样一个数列:
$f(1) = 1,f(2) = 1,f(3) = 2,f(4) =3 ,f(i) = f(i-1) + f(i-2)$
求对于某一个$Fibonacci$数$Fi$,有多少个$Fj$能够整除$Fi$ ($i$可以等于$j$),
以及这些数的平方和。

$Solution$
首先我们对于$Fibonacci$数列需要了解一些性质,我们需要知道$gcd(f(i),f(j)) = f(gcd(i,j))$
然后就好办了,这两个问题就变为求一个数的约数的个数和约数的平方和了
这个东西可以筛出来,我用的是线性筛

首先我们需要明确一个事情,在线性筛的时候筛掉一个数字,一定是通过他最小的一个因数筛掉他的
考虑$i$筛到了$prime_j$,那么就可以分为两种情况进行讨论
令 $A = prime_ji$,用$f(i)$表示其因子的平方和,$g(i)$表示其因子的个数
1.$i%prime_j!=0$
这时候可以说明$i$里面并没有$prime_j$,但是$prime_j$又是他的最小的质因子,所以我们可以把它的因子分为两部分,一部分不含最小的质因子,另一部分是上一部分乘上这个最小的质因子的东西。显然这两部分是根本没有交集的,所以$g(A) = 2
g(i),f(A) = f(i)*(prime_j^2+1)$
2.$i%prime_j==0$
这个时候说明$i$中其实也有$prime_j$这个因子,所以再通过转移十分麻烦,直接考虑重新计算,我们还是要把他的因子分为两部分,一部分不含最小的质因子,另一部分是因子的几次幂乘上去的,显然这两部分不会有交集。
令$B$为$A$除掉他所有的质因子剩下的数字,然后我们进行计算
首先
$f(i) = f(B)·\sum_{k=0}^{cnt(i)}{(prime_{MIN}^2)^k}$
$f(A) = f(B)·\sum_{k=0}^{cnt(i)+1}{(prime_{MIN}^2)^k}$

然后把上面的式子带到下面的去
得到
$f(A) = f(i)*prime_{MIN}^2+f(B)$
其中$cnt(i)$指$i$中含有最小质因子的个数,随便维护一下就行了
对于$B$也是随便维护就行……
然后是$g$数组的转移,但是我们已经明白了怎么算一个数字的$g$,我们又有了一个数中含有多少个质因子,所以就可以直接乘除加减算一下就行了,可以看一下我的代码

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
typedef long long LL;
const int N = 1e7+5;
const int mod = 1000000007;

using namespace std;

int prime[N];
bool flag[N];
int f[N],g[N];
int T[N];
int tmp[N];
int cnt = 0;

void pre(int n)
{
    f[1] = g[1]  = 1;
    int i=1,j=2;
    for(i=2;i<=n;++i)
    {
        if(!flag[i])
        {
            prime[++cnt] = i;
            f[i] = ((LL)i*i%mod+1)%mod;
            g[i] = 2;
            T[i] = 1;
            tmp[i] = 1;
        }
        for(j=1;(LL)prime[j]*i <= n;++j)
        {
            flag[prime[j]*i] = 1;
            if(i%prime[j]!=0)
            {   
                g[prime[j]*i] = 2*g[i];
                f[prime[j]*i] = (LL)f[i]*((LL)prime[j]*prime[j]%mod+1)%mod;
                T[prime[j]*i] = i; 
                tmp[prime[j]*i] = 1;
            }
            else
            {
                g[prime[j]*i] = g[i]/(tmp[i]+1)*(tmp[i]+2);
                f[prime[j]*i] = ((LL)f[i]*prime[j]%mod*prime[j]%mod+(LL)f[T[i]])%mod;
                T[prime[j]*i] = T[i];
                tmp[prime[j]*i] = tmp[i]+1;
                break;              
            }
        }
    }
}

void test()
{
    for(int i=1;i<=100;++i)
        cout << g[i] << " "  << f[i] << endl;
    
}

int main()
{
    int Q;
    cin >> Q;
    LL tmp , A, B ,C;
    cin >> tmp >> A >> B >> C;
    pre(1e7);
    
//  test();
    
    LL ans1 = 0;
    LL ans2 = 0;
    while(Q--)
    {
        (ans1 += g[tmp])%=mod;
        (ans2 += f[tmp])%=mod;
        if(tmp &1) ans1 ++, ans2 += 4;
        ((tmp *= A) += B )%=C;
        tmp++;
    }
    cout << ans1 << endl << ans2 << endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP