Light oj 1236

题目链接：http://lightoj.com/volume_showproblem.php?problem=1236

题意很好懂，就是让你求lcm(i , j)的i与j的对数。

可以先预处理1e7以内的素数，然后用来筛选出能被n整除的所有的素数以及素数的个数，时间复杂度是小于根号的。然后用DFS或者BFS选出所有的约数(不会很大)。

现在要是直接2个for利用gcd筛选lcm(x,y)==n的个数的话肯定超时，所以这里把每个素数看作一个位，比如:2 3 5这3个素因子，那我2可以看作2进制上的第一位(1)，3第二位(10)...那一个约数就可以表示素因子相乘也可以表示成一个二进制数比如6表示成(11)，那么要是两个约数的二进制数的'|'值等于n，那么lcm就等于n。然后处理出每个约数对应的二进制数。注意一点的是约数里的某个素因子不满其最大个数的话就表示为0。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <vector>
  5 #include <algorithm>
  6 #include <queue>
  7 using namespace std;
  8 typedef long long LL;
  9 typedef pair <LL , int> P;
 10 const int MAXN = 1e7 + 1000;
 11 vector <P> G;
 12 vector <LL> res;
 13 bool prime[MAXN];
 14 int p[MAXN / 9];
 15 
 16 void init() {
 17     prime[1] = true;
 18     int cont = 0;
 19     for(int i = 2 ; i < MAXN ; i++) {
 20         if(!prime[i]) {
 21             p[++cont] = i;
 22             for(int j = i * 2 ; j < MAXN ; j += i) {
 23                 prime[j] = true;
 24             }
 25         }
 26     }
 27 }
 28 /*
 29 DFS
 30 void dfs(int dep , int end , LL num) {
 31     if(dep == end) {
 32         res.push_back(num);
 33         return ;
 34     }
 35     LL temp = (1 << (dep));
 36     for(int i = 0 ; i < G[dep].second ; i++) {
 37         dfs(dep + 1 , end , num);
 38     }
 39     dfs(dep + 1 , end , num + temp);
 40 }
 41 */
 42 void bfs(int end) {
 43     queue <P> que;
 44     while(!que.empty()) {
 45         que.pop();
 46     }
 47     que.push(P(0 , 0));
 48     while(!que.empty()) {
 49         P temp = que.front();
 50         que.pop();
 51         if(temp.second == end) {
 52             res.push_back(temp.first);
 53         }
 54         else {
 55             for(int i = 0 ; i <= G[temp.second].second ; i++) {
 56                 if(i == G[temp.second].second) {
 57                     que.push(P(temp.first + (1 << temp.second) , temp.second + 1));
 58                 }
 59                 else {
 60                     que.push(P(temp.first , temp.second + 1));
 61                 }
 62             }
 63         }
 64     }
 65 }
 66 
 67 int main()
 68 {
 69     init();
 70     int t;
 71     LL n;
 72     scanf("%d" , &t);
 73     for(int ca = 1 ; ca <= t ; ca++) {
 74         scanf("%lld" , &n);
 75         printf("Case %d: " , ca);
 76         if(n == 1) {
 77             printf("1
");
 78             continue;
 79         }
 80         res.clear();
 81         G.clear();
 82         for(int i = 1 ; (LL)p[i]*(LL)p[i] <= n ; i++) {
 83             if(n % p[i] == 0) {
 84                 int cont = 0;    
 85                 while(n % p[i] == 0) {
 86                     n /= p[i];
 87                     cont++;
 88                 }
 89                 G.push_back(P((LL)p[i] , cont));
 90             }
 91         }
 92         if(n > 1)
 93             G.push_back(P(n , 1));
 94         int ans = (1 << G.size()) - 1 , cont = 0;
 95         //dfs(0 , G.size() , 0);
 96         bfs(G.size());
 97         for(int i = 0 ; i < res.size() ; i++) {
 98             for(int j = 0 ; j < res.size() ; j++) {
 99                 if((res[i] | res[j]) == ans) {
100                     cont++;
101                 }
102             }
103         }
104         printf("%d
" , cont / 2 + 1);
105     }
106 }