HDU 6108 小C的倍数问题

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

• 题意：求小于1e9时有多少个数（设cnt个ans满足）满足：

1. 对于每一个数，能整除ans  当且仅当这个数每位之和是ans的倍数；
2. 要求在p进制下

• 题解：这个数是n

x1+x2*p+x3*p^2+.......=n  

n%B==0且要求(x1+x2+x3+.....)%B==0

那么--->( x2*(p-1)+x3*(p^2-1)+.....)%B==0  -->  { x2*(p-1) + x3*( p -1 )*( p+1 ) + ..... } % B == 0

当 B 能被 p-1 整除时 一定符合等式

即求 p-1 的因子个数，注意按  i<=sqrt(n) 来算，不然会超时。

这种做法原理是， 以这个数的平方根为界，若小于这个界限有一个数能被n整除，那么大于这个界限一定也存在一个数能

被整除。所以当这个数为平方数时就存在一个ans会重复

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve(ll n)
{
	int cnt=0;
	for(ll i=1;i<=sqrt(n);i++)
	   {
	   	 if(n%i==0&&i*i!=n)cnt+=2;//每次找到能整除的就加二
	   	 else if(n%i==0)cnt++;//这个数本身是平方数就减一
	   }
	   printf("%lld\n",cnt);
}
int main()
{
	int t;
	ll	n;
	scanf("%d",&t);
	while(t--)
	{
	 scanf("%lld",&n);
	  solve(n-1);
    }
	
	return 0;
}