DIV2 1000pt
题意：给定两个集合A和B，A = {b1*q1i | 0 <= i <= n1-1}，B = {b2*q2i | 0 <= i <= n2-1}，问将AB两个集合合并之后的集合中元素的个数。(注意，每个集合中每个元素只能有一个)。其中0 <= b1,b2,q1,q2 <= 5*10^8，1 <= n1,n2 <= 10^5。
解法：首先，我们称b = 0或者q = 0或者q = 1的集合为特殊集合，因为特殊集合中最多有两个元素。若至少有一个集合为特殊集合，则此问题容易解决。下面考虑两个集合都不为特殊集合的情况。
其实，如果不是A和B中的数太大，我们可以将他们每个都求出来，然后放到一个set<long long>里面，返回set.size()即可，时间复杂度O(n1 + n2)。我们需要找到一种表示这些大数的方法。考虑整数的唯一分解式。
每个整数可以表示成(a1^p1) * (a2^p2) * (a3^p3) *..* (ak^pk)的形式，也就是说，我们只需要统一所有会用到的质数，然后把p1,p2..pk放到一个vector里面，就可以表示每个整数。然后用一个set<vector<long long> >即可统计元素的个数。
tag: math, set
// BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "GeometricProgressions.cpp"
#include <sstream>
#include <stdexcept>
#include <functional>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <cctype>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <set>
#include <queue>
#include <bitset>
#include <list>
#include <string>
#include <utility>
#include <map>
#include <ctime>
#include <stack> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define PB push_back
#define SZ(v) ((int)(v).size())
#define zero(x) (((x)>0?(x):-(x))<eps)
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl
#define CINBEQUICKER std::ios::sync_with_stdio(false) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long int64; const double eps = 1e-;
const double PI = atan(1.0)*;
const int maxint = ;
const int N = ;
const int M = ; int an[][N];
int tmp_sz;
int64 bn[][N]; int inte_dev(int x, int* an, int64* bn)
{
int all = -;
for (int i = ; i*i <= x;){
if (!(x%i)){
an[++all] = i;
bn[all] = ;
}
while (!(x%i)){
++ bn[all];
x /= i;
}
if (i == ) ++ i;
else i += ;
}
++ all;
if (x != ){
an[all] = x;
bn[all++] = ;
}
return all;
} int gao(int64 x, int a)
{
int ret = ;
while (!(x % a)){
x /= a;
++ ret;
}
return ret;
} VI vadd(VI a, VI b)
{
VI ret; ret.clear();
for (int i = ; i < tmp_sz; ++ i)
ret.PB (a[i]+b[i]);
return ret;
} class GeometricProgressions
{
public:
int count(int aa, int b, int n, int c, int d, int m){
int64 a[];
a[] = aa; a[] = b; a[] = c; a[] = d;
if (!a[] || !a[] || a[] == ){
swap (a[], a[]); swap (a[], a[]); swap (n, m);
}
if (!a[] || !a[] || a[] == ){
set<int64> tmp;
tmp.insert(a[]);
if (n > ) tmp.insert(a[]*a[]); int cnt = , sz_tmp = tmp.size();
int64 now = a[];
for (int i = ; i < m; ++ i){
if (tmp.count(now)) ++ cnt;
else tmp.insert(now);
now *= a[];
if (now > 25e16)
return m + sz_tmp - cnt;
}
return tmp.size();
} int64 all[];
for (int i = ; i < ; ++ i)
all[i] = inte_dev(a[i], an[i], bn[i]); set<int> tmp;
VI tt; tt.clear();
for (int i = ; i < ; ++ i)
for (int j = ; j < all[i]; ++ j)
if (!tmp.count(an[i][j])){
tmp.insert (an[i][j]);
tt.PB (an[i][j]);
} vector<int> v[];
for (int i = ; i < ; ++ i)
v[i].clear();
tmp_sz = tmp.size();
for (int i = ; i < ; ++ i)
for (int j = ; j < tmp_sz; ++ j)
v[i].PB (gao(a[i], tt[j])); set<VI > ans;
ans.erase(ans.begin(), ans.end());
VI now = v[];
for (int i = ; i < n; ++ i){
if (!ans.count(now)) ans.insert(now);
now = vadd(now, v[]);
}
now = v[];
for (int i = ; i < m; ++ i){
if (!ans.count(now)) ans.insert(now);
now = vadd(now, v[]);
}
return ans.size();
} // BEGIN CUT HERE
public:
//void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); }
void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0();}
private:
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
void test_case_0() { int Arg0 = ; int Arg1 = ; int Arg2 = ; int Arg3 = ; int Arg4 = ; int Arg5 = ; int Arg6 = ; verify_case(, Arg6, count(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5)); }
void test_case_1() { int Arg0 = ; int Arg1 = ; int Arg2 = ; int Arg3 = ; int Arg4 = ; int Arg5 = ; int Arg6 = ; verify_case(, Arg6, count(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5)); }
void test_case_2() { int Arg0 = ; int Arg1 = ; int Arg2 = ; int Arg3 = ; int Arg4 = ; int Arg5 = ; int Arg6 = ; verify_case(, Arg6, count(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5)); }
void test_case_3() { int Arg0 = ; int Arg1 = ; int Arg2 = ; int Arg3 = ; int Arg4 = ; int Arg5 = ; int Arg6 = ; verify_case(, Arg6, count(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
// freopen( "a.out" , "w" , stdout );
GeometricProgressions ___test;
___test.run_test(-);
return ;
}
// END CUT HERE