一个十进制数 1≤n≤1012 ，现在用base进制来表示，问有多少种表示方法使得最后一位上的数为0？ 等同于求出n有多少种约数，即 n%base==0 ；
开始想的是枚举sqrt内的数，TLE了，因为有10000组数据。。。。 有一个表达式 x=px11∗px22∗px33... 其中 pi 是素数， xi 为正整数，这样我们就能算出约数的个数了。。。 answer=(x1+1)∗(x2+1)∗...−1
#include <iostream> #include <cstring> #include <cstdio> using namespace std; int nCase = 0; const long long maxn = 1e6 + 10; long long prime[maxn]; bool vis[maxn]; //prime[0]记录素数的个数，素数从prime[1]开始存 inline void init() { memset(vis, false, sizeof vis); for (long long i = 2;i < maxn;++i) { if (!vis[i]) { for (long long j = i * i;j < maxn;j += i) vis[j] = true; prime[++prime[0]] = i; } } } int main(int argc, const char * argv[]) { // freopen("/Users/jamesqi/Desktop/in.txt","r",stdin); // freopen("/Users/jamesqi/Desktop/out.txt","w",stdout); // ios::sync_with_stdio(false); // cout.sync_with_stdio(false); // cin.sync_with_stdio(false); init(); int kase;cin >> kase; while(kase--) { long long n;cin >> n; long long ans = 1; long long num = n; for (int i = 1;i <= prime[0] && prime[i] * prime[i] <= num;++i) { if (num % prime[i] == 0) { int temp = 0; while(num % prime[i] == 0) { ++temp; num /= prime[i]; } ans *= (temp + 1); } } // ans *= 2; if (num > 1) ans *= 2; // ans *= (1 + 1); //ans - 1 because of the basic number 1 printf("Case %d: %lld\n", ++nCase, ans - 1); } // showtime; return 0; }