LCM的个数 (LCM Cardinality,UVa 10892)

 1 #include <iostream>
 2 #include <string.h>
 3 #include <string>
 4 #include <fstream>
 5 #include <algorithm>
 6 #include <stdio.h>
 7 #include <vector>
 8 #include <queue>
 9 #include <set>
10 #include <cmath>
11 using namespace std;
12 const double eps = 1e-8;
13 const int INF=0x7fffffff;
14 #define MAXN 10000007
15 typedef long long LL;
16 LL vis[MAXN];
17 LL prime[MAXN];
18 
19 void sieve(LL n)
20 {
21     LL m=(LL)sqrt(n+0.5);
22     memset(vis,0,sizeof(vis));
23     for(LL i=2;i<=m;i++)if(!vis[i])
24     for(LL j=i*i;j<=n;j+=i)vis[j]=1;
25 }
26 
27 LL gen_prime(LL n)
28 {
29     sieve(n);
30     LL c=0;
31     for(LL i=2;i<=n;i++)if(!vis[i])
32         prime[c++]=i;
33     return c;
34 }
35 
36 LL gcd(LL a,LL b)
37 {
38     return b==0?a:gcd(b,a%b);
39 }
40 
41 
42 int main()
43 {
44     LL n;
45     LL N=gen_prime(10000001);
46     while(scanf("%lld",&n),n)
47     {
48         LL tempn=n;
49         LL ans=1;
50         for(int i=0;i<N&&n>=prime[i];i++)
51         {
52             int temp=0;
53             while(tempn%prime[i]==0)
54             {
55                 tempn/=prime[i];
56                 temp++;
57             }
58 
59             ans*=(2*temp+1);
60         }
61         ans=(ans-1)/2+1;
62         printf("%lld %lld
",n,ans);
63     }
64     return 0;
65 }
找规律……