Description:

定义函数

对于输入的 求出满足 的正整数 的个数。

Solution:

首先,假设

只有 时,才会有

所以

这样的话,这道题目就简单了,首先记录下 的所有因数,从小到大存在 中。

表示当 的正整数 有多少个。

筛出 以内的质数,判断 的约数 是不是某个质数的某次方加一,如果是,

之后对于 ,如果 并且 ,那么

然后这题就做完了,其中可以用 之类的简化代码。

Code:

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>

using namespace std;

vector <long long> G[100010];
int prime[100010]={0};
int pp=0;
int hash[1000010]={0};
long long N=0;
long long hehe[10010]={0};
int hehep=0;
int F[8000]={0};
map <long long,int> FF;


void P_prime()
{
    for(int i=2;i<=1000000;i++)
    {
        if(hash[i]==0) prime[++pp]=i;
        for(int j=1;j<=pp && i*prime[j]<=1000000;j++)
        {
            hash[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
    return;
}

void check(int k)
{
    long long gg=prime[k];
    for(;gg<=1000000;gg*=prime[k])
    {
        if(N%((int)gg+1)==0)
            G[k].push_back((int)gg+1);
    }
    return;
}

bool isprime(long long k)
{
    for(int i=1;i<=pp;i++)
        if(k%prime[i]==0)
            return false;
    return true;
}

void isprimepower(long long k)
{
    long long ff=k;
    for(int i=1;i<=pp;i++)
        if(k%prime[i]==0)
        {
            for(;ff%prime[i]==0 && ff>1;ff/=prime[i]);
            if(ff==1)
                G[i].push_back(k+1);
            return;
        }
    return;
}

int main()
{
    cin>>N;
    P_prime();
    for(int i=1;i<=pp;i++)
        check(i);
    hehe[++hehep]=1;
    for(int i=2;(long long)i*i<=N;i++)
    {
        if(N%i==0)
        {
            hehe[++hehep]=i;
            hehe[++hehep]=N/i;
        }
    }
    if(N!=1) hehe[++hehep]=N;
    sort(hehe+1,hehe+hehep+1);
    for(int i=1;i<=hehep;i++)
    {
        FF[hehe[i]]=i;
        if(hehe[i]-1>1000000)
        isprimepower(hehe[i]-1);
    }
    F[1]=1;
    for(int i=1;i<=pp;i++)
    {
        for(int j=hehep;j>=1;j--)
        {
            int Si=G[i].size();
            for(int p=0;p<Si;p++)
            {
                map <long long,int>::iterator it;
                if(N%(hehe[j]*G[i][p])!=0) continue;
                it=FF.find(hehe[j]*G[i][p]);
                if(it!=FF.end())
                    F[it->second]+=F[j];
            }
        }
    }
    for(int i=1;i<=hehep;i++)
    {
        if(hehe[i]-1<=1000000) continue;
        if(isprime(hehe[i]-1)==false) continue;
        for(int j=hehep;j>=1;j--)
        {
            map <long long,int>::iterator it;
            it=FF.find(hehe[j]*hehe[i]);
            if(it!=FF.end())
                F[it->second]+=F[j];
        }
    }
    printf("%d",F[hehep]);
    return 0;
}