题目链接：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。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair <LL , int> P;
const int MAXN = 1e7 + ;
vector <P> G;
vector <LL> res;
bool prime[MAXN];
int p[MAXN / ]; void init() {
prime[] = true;
int cont = ;
for(int i = ; i < MAXN ; i++) {
if(!prime[i]) {
p[++cont] = i;
for(int j = i * ; j < MAXN ; j += i) {
prime[j] = true;
}
}
}
}
/*
DFS
void dfs(int dep , int end , LL num) {
if(dep == end) {
res.push_back(num);
return ;
}
LL temp = (1 << (dep));
for(int i = 0 ; i < G[dep].second ; i++) {
dfs(dep + 1 , end , num);
}
dfs(dep + 1 , end , num + temp);
}
*/
void bfs(int end) {
queue <P> que;
while(!que.empty()) {
que.pop();
}
que.push(P( , ));
while(!que.empty()) {
P temp = que.front();
que.pop();
if(temp.second == end) {
res.push_back(temp.first);
}
else {
for(int i = ; i <= G[temp.second].second ; i++) {
if(i == G[temp.second].second) {
que.push(P(temp.first + ( << temp.second) , temp.second + ));
}
else {
que.push(P(temp.first , temp.second + ));
}
}
}
}
} int main()
{
init();
int t;
LL n;
scanf("%d" , &t);
for(int ca = ; ca <= t ; ca++) {
scanf("%lld" , &n);
printf("Case %d: " , ca);
if(n == ) {
printf("1\n");
continue;
}
res.clear();
G.clear();
for(int i = ; (LL)p[i]*(LL)p[i] <= n ; i++) {
if(n % p[i] == ) {
int cont = ;
while(n % p[i] == ) {
n /= p[i];
cont++;
}
G.push_back(P((LL)p[i] , cont));
}
}
if(n > )
G.push_back(P(n , ));
int ans = ( << G.size()) - , cont = ;
//dfs(0 , G.size() , 0);
bfs(G.size());
for(int i = ; i < res.size() ; i++) {
for(int j = ; j < res.size() ; j++) {
if((res[i] | res[j]) == ans) {
cont++;
}
}
}
printf("%d\n" , cont / + );
}
}