原来就是对两个数分别因数分解,然后分别放到两个集合里,求合并后的集合的大小。再求每个数与另一个集合中该数的幂级数之差,如果另一个集合中没有这个数,就相当于这个集合中这个数的幂级数是0,最后把这些差的绝对值相加就是结果。
/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 100000000
#define LOCA
#define PI acos(-1.0)
using namespace std;
bool tag[1000011];
int p[1000011];
int cnt;
void get_prime()
{
cnt = 0;
tag[1] = 1;
for (int i = 2; i < 1000005; i++)
{
if (!tag[i])
p[cnt++] = i;
for (int j = 0; j < cnt && p[j] * i < 1000005; j++)
{
tag[i*p[j]] = 1;
if (i % p[j] == 0)
break;
}
}
}
int main()
{
#ifdef LOCAL
freopen("ride.in","r",stdin);
freopen("ride.out","w",stdout);
#endif
int a, b, i, cas = 0;
get_prime();
while(scanf("%d%d", &a, &b) != EOF)
{
if(a == 0 && b == 0) break;
int ans = 0;
int count = 0;
for(i = 0; i < cnt && (p[i] <= a || p[i] <= b); i++)
{
bool fg1 = false;
bool fg2 = false;
int ct1 = 0;
int ct2 = 0;
if(a % p[i] == 0)
{
fg1 = true;
while(a % p[i] == 0)
{
a /= p[i];
ct1++;
}
}
if(b % p[i] == 0)
{
fg2 = true;
while(b % p[i] == 0)
{
b /= p[i];
ct2++;
}
}
if(fg1 || fg2)
{
count++;
ans += abs(ct1 - ct2);
}
}
printf("%d. %d:%d\n", ++cas, count, ans);
}
return 0;
}
分享到:
相关推荐
北大POJ1936-All in All 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ1094-Sorting It All Out 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
北大POJ1159-Palindrome 解题报告+AC代码
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1001答案
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
POJ2968代码有用,欢迎下载,POJ代码
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告