2015 Multi-University Training Contest 3 1002 RGCDQ RGCDQ Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=5317
Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=5317
Mean:
定义函数f(x)表示：x的不同素因子个数。
如：f(2) = 1, f(6) = 2；
给定L和R(L<=i<j<=R),求区间内任意不相等的两个数f(x)的最大公约数的最大值。
analyse:
因为2*3*5*7*11*13*17 >1e6,所以f(x)的值最大为7;
我们先打表求出每个数的f(x)值；
f[i][j]表示2~i中质因数个数为j的个数。
然后再利用前缀和f[r][i] - f[l-1][i],求出区间[l, r]的值。
Time complexity: O(NlogN)
Source code:
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-07-28-19.01
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
int T, a, b;
int f[1000009][10];
const int NN = 1000005;
int p[NN];
bool v[NN];
void cntPrimeNum()
{
for( int i = 2; i < NN; ++i )
{
if( !v[i] )
for( int j = i; j < NN; j += i )
{
v[j] = true;
++p[j];
}
}
}
int main()
{
cntPrimeNum();
for( int i = 1; i < NN; ++i )
for( int j = 7; j > 0; --j )
if( p[i] == j ) f[i][j] = 1;
for( int i = 1; i <= 1000000; ++i )
for( int j = 1; j <= 7; ++j )
f[i][j] += f[i - 1][j];
scanf( "%d", &T );
while( T-- )
{
int ans = 1;
scanf( "%d %d", &a, &b );
for( int i = 7; i > 0; --i )
{
if( f[b][i] - f[a - 1][i] > 1 )
{
ans = i;
break;
}
}
printf( "%d ", ans );
}
return 0;
}
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-07-28-19.01
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
int T, a, b;
int f[1000009][10];
const int NN = 1000005;
int p[NN];
bool v[NN];
void cntPrimeNum()
{
for( int i = 2; i < NN; ++i )
{
if( !v[i] )
for( int j = i; j < NN; j += i )
{
v[j] = true;
++p[j];
}
}
}
int main()
{
cntPrimeNum();
for( int i = 1; i < NN; ++i )
for( int j = 7; j > 0; --j )
if( p[i] == j ) f[i][j] = 1;
for( int i = 1; i <= 1000000; ++i )
for( int j = 1; j <= 7; ++j )
f[i][j] += f[i - 1][j];
scanf( "%d", &T );
while( T-- )
{
int ans = 1;
scanf( "%d %d", &a, &b );
for( int i = 7; i > 0; --i )
{
if( f[b][i] - f[a - 1][i] > 1 )
{
ans = i;
break;
}
}
printf( "%d ", ans );
}
return 0;
}