本原串

思路：

反向想将总的个数减去不符合要求的个数。我们枚举n的约数，然后把n平均分，就可以构成不符合要求的串，\(g[i]\)表示循环节长为i约数的个数\(2^i\)，我们要求循环节为\(i\)的\(f[i]\)，那么可以想到莫比乌斯，但在这里莫比乌斯不好些范围有些大，所以我们用dp的方式去重\(f[i] -= g[i] - f[j](j| i)\)复杂度为\(m*log(m)\) (\(m\)为\(n\)的约数个数).

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL mod = 2008;

int quick(int n,int m);

map<int,int>my;

int ans[1000000];

int f[1000000];

int slove(int n);

int main(void)

{

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        printf("%d\n",slove(n));

    }

    return 0;

}

int quick(int n,int m)

{

    int ans = 1;

    while(m)

    {

        if(m&1)

            ans = ans*n%mod;

        n = n*n%mod;

        m>>=1;

    }

    return ans;

}

int slove(int n)

{

    int sum = 0;

    int cn = 0;

    memset(f,0,sizeof(f));

    for(int i = 1; i <= sqrt(n); i++)

    {

        if(n%i == 0)

        {

            ans[cn++] = i;

            if(i!=n/i)

                ans[cn++] = n/i;

        }

    }

    sort(ans,ans+cn);

    cn--;

    for(int i = 0; i < cn; i++)

    {

        f[i] = f[i]+quick(2,ans[i]);

        f[i]%=mod + mod;

        f[i]%=mod;

        for(int j = i+1; j < cn; j++)

        {

            if(ans[j]%ans[i] == 0)

            {

                f[j] = ((f[j] - f[i])%mod + mod)%mod;

            }

        }

    }

    sum = quick(2,n);

    for(int i = 0; i < cn; i++)

    {

        sum = sum - f[i];

        sum %= mod;

    }

    return (sum + mod)%mod;

}

巴特西

本原串(hdu 2197)

本原串

思路：

最新文章

热门文章