正文
hdu 6108 小C的倍数问题
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
小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
10
Sample Output
3
思路:若是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 ;
}