小C的倍数问题

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 277 Accepted Submission(s):
137

Problem Description

根据小学数学的知识，我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之，如果一个数每一位加起来是3的倍数，则这个数肯定是3的倍数。

现在给定进制P，求有多少个B满足P进制下，一个正整数是B的倍数的充分必要条件是每一位加起来的和是B的倍数。

Input

第一行一个正整数T表示数据组数(1<=T<=20)。

接下来T行，每行一个正整数P(2
< P < 1e9)，表示一组询问。

Output

对于每组数据输出一行，每一行一个数表示答案。

Sample Input

1
10

Sample Output

思路：若是p进制，设一个数为^_a1a2a3,若a1a2a3%B==0可以表达成(a1*p^2+a2*p+a3)%B==0----------1式

并且按题意，(a1+a2+a3)%B==0---------2式

设p=k*B+x,代入1式，并且与2式比较，待定系数求解得x==1,也就是说p-1=k*B,那么B一定p-1的因子，找到(p-1)所有的因子即是所求。

AC代码：

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<queue>

#include<set>

#include<vector>

#include<cstring>

#include<string>

#include<cmath>

using namespace std;

vector<int>divisor(int n) {

    vector<int>res;

    for (int i = ; i*i < n;i++) {

        if (n%i == ) {

            res.push_back(i);

            if (i != n / i)res.push_back(n / i);

        }

    }

    return res;

}

int p;

int main() {

    int t;

    scanf("%d",&t);

    while (t--) {

        scanf("%d",&p);

        vector<int>vec = divisor(p - );

        printf("%d\n",vec.size());

    }

    return ;

}

巴特西

hdu 6108 小C的倍数问题

小C的倍数问题

最新文章

热门文章