HDU 6108 小C的倍数问题【数学】（2017"百度之星"程序设计大赛

小C的倍数问题

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

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

3

Source

2017"百度之星"程序设计大赛 - 初赛（A）

Recommend

liuyiding   |   We have carefully selected several similar problems for you:  6113 6112 6111 6110 6109

Statistic | Submit | Discuss | Note

题目链接：

　　http://acm.hdu.edu.cn/showproblem.php?pid=6108

题目大意：

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

题目思路：

　　【数学】

　　设x=a₀+a₁p+a₂p²+...=a0+a1+a2+...+a1(p-1)+a2(p²-1)+...，后面的式子都能提出p-1因子，因此a0+a1+a2+...若含有p-1因子一定满足，

　　所以p-1一定是一个解，再看p-1的所有约数，均符合要求。故求p-1的因子个数。

 1 /****************************************************
 2 
 3     Author : Coolxxx
 4     Copyright 2017 by Coolxxx. All rights reserved.
 5     BLOG : http://blog.csdn.net/u010568270
 6 
 7 ****************************************************/
 8 #include<bits/stdc++.h>
 9 #pragma comment(linker,"/STACK:1024000000,1024000000")
10 #define abs(a) ((a)>0?(a):(-(a)))
11 #define lowbit(a) (a&(-a))
12 #define sqr(a) ((a)*(a))
13 #define mem(a,b) memset(a,b,sizeof(a))
14 const double EPS=0.00001;
15 const int J=10;
16 const int MOD=100000007;
17 const int MAX=0x7f7f7f7f;
18 const double PI=3.14159265358979323;
19 const int N=104;
20 const int M=1004;
21 using namespace std;
22 typedef long long LL;
23 double anss;
24 LL aans;
25 int cas,cass;
26 int n,m,lll,ans;
27 int prime[M/3],e[M/3],div_num[M];         // e[i]表示第i个素数因子的个数
28 bool flag[M];
29 void get_prime()
30 {
31     int i,j,k;
32     mem(flag,0);
33     k=0;
34     for(i=2;i<M;i++)
35     {
36         if(!flag[i])
37         {                            
38             prime[k++]=i;
39             e[i]=1;
40             div_num[i]=2;                     //素数的约数个数为2
41         }
42         for(j=0;j<k&&i*prime[j]<M;j++)
43         {
44             flag[i*prime[j]]=true;
45             if(i%prime[j]==0)
46             {
47                 div_num[i*prime[j]]=div_num[i]/(e[i]+1)*(e[i]+2);
48                 e[i*prime[j]]=e[i]+1;
49                 break;
50             }
51             else
52             {
53                 div_num[i*prime[j]]=div_num[i]*div_num[prime[j]];
54                 e[i]=1;
55             }
56         }
57     }
58 } 
59 int main()
60 {
61     #ifndef ONLINE_JUDGE
62 //    freopen("1.txt","r",stdin);
63 //    freopen("2.txt","w",stdout);
64     #endif
65     int i,j,k;
66     int x,y,z;
67 //    for(scanf("%d",&cass);cass;cass--)
68     for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
69 //    while(~scanf("%d",&n))
70     {
71         scanf("%d",&n);
72         n--;
73         aans=1;
74         m=n;
75         for(int q=2;q*q<=n;q++)
76         {
77             x=1;
78             while(m%q==0)
79             {
80                 m/=q;
81                 x++;
82             }
83             aans*=x;
84         }
85         if(m!=1)
86             aans*=2;
87         cout<<aans<<endl;
88     }
89     return 0;
90 }
91 /*
92 //
93 
94 //
95 */

View Code

HDU 6108 小C的倍数问题 【数学】 （2017"百度之星"程序设计大赛

小C的倍数问题

HDU 6108 小C的倍数问题【数学】（2017"百度之星"程序设计大赛