HDU6108 2017百度之星 初赛A轮A

题目在这里>_<

题意

根据小学数学的知识，我们知道一个正整数$x$是$3$的倍数的条件是$x$每一位加起来的和是$3$的倍数。反之，如果一个数每一位加起来是$3$的倍数，则这个数肯定是$3$的倍数。
现在给定进制$P$，求有多少个$B$满足$P$进制下，一个正整数是$B$的倍数的充分必要条件是每一位加起来的和是$B$的倍数。

思路

显然,$B$满足题目条件当且仅当，$P \equiv 1 \pmod B$。也就是说，寻找有多少数能够整除$P-1$。那么我们直接对$P-1$做因式分解即可求得答案。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
//#define test
using namespace std;
const int Nmax=1e6+7;
typedef long long ll;
int n;
int is_prime[Nmax];
int prime[Nmax];
int prime_cnt;
void get()
{
    for(int i=2;i<Nmax;i++)
        is_prime[i]=1;
    for(long long i=2;i<Nmax;i++)
    {
        if(is_prime[i])
        {
            prime[++prime_cnt]=i;
        }
        for(int j=1;j<=prime_cnt;j++)
        {
            if(i*prime[j]>=Nmax)
                break;
            is_prime[i*prime[j]]=0;
            if(i%prime[j]==0)
                break;
        }
    }
}


int main()
{
    #ifdef test
    #endif
    int t;
    get();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        n--;
        int m=n;
        int ans=1;
        for(int i=1;i<=prime_cnt && prime[i]*prime[i]<=m;i++)
        {
            if(m%prime[i]==0)
            {
                int now=0;
                while(m%prime[i]==0)
                {
                    m/=prime[i];
                    now++;
                }
                ans=ans*(now+1);
            }
        }
        if(m!=1)
            ans=ans*2;
        //if(i==n)
            //now--;
        //printf("i:%d %d\n",i,now);
        printf("%d\n",ans);

    }
    return 0;
}