3055 - 雯神与狗不得不说的故事3
上回说到雯神现在不怕狗了反而喜欢狗了。今天雯神走到了一个奇怪的地方，这个地方有好多狗狗，并且有n种不同的狗狗，每只狗狗上有一个数字，雯神为了知道有多少只狗狗特地的数了一下，发现写着ai的狗狗有ai^mi只。但是实在太多了。雯神决定用一个数来表示这些狗狗，但是因为雯神数学没学好，所以连求LCM都不会，谁来帮帮雯神。其实是雯神觉得LCM太简单了，不想自己动手解决而以啦！！！
求 u =LCM( a[1] ^ m[1], a[2] ^ m[2], ... , a[n] ^ m[n] )%(10^9+7)。
<span style="line-height:1.5;">Ps: LCM 即（Least Common Multiple）</span>
<br />
Input
多组输入。
对于每组数据：
第一行一个n。( 2 <= n && n <= 10 )
下面一行n个数，依次表示 m[1], ... , m[n] ( m[i] >=1 && m[i] <= 1000 , i = 1...n )
再下一行n个数，表示a[1], ... , a[n] ( a[i] >= 1 && a[i] <= 100000, i = 1...n )
Output
对于每组数据，输出一行，该行包含一个整数u%(10^9+7)的结果。
Examples
Input
3 1 1 1 1 2 3
Output
6
Solution C++
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> using namespace std; #define max( a, b ) ( (a) > (b) ? (a) : (b) ) #define min( a, b ) ( (a) < (b) ? (a) : (b) ) #define llint long long #define endl '\n' #define WS ' ' int n; // 2 <= n <= 10 #define N 12 int a[N]; // 2 <= a[i] <= 10 ^ 5 int m[N]; // 2 <= m[i] <= 10 ^ 3 // find: lcm( a[1] ^ m[1], a[2] ^ m[2], ... , a[n] ^ m[n] ) % (10 ^ 9 + 7) #define MAXA 100010 bool ip[MAXA]; llint pr[MAXA >> 1], nop; void init_ip() { memset( ip, true, sizeof(ip) ); ip[0] = ip[1] = false; nop = 0; for( llint i = 2; i < MAXA; i ++ ) { if( ip[i] ) { pr[nop ++] = i; for( llint j = i * i; j < MAXA; j += i ) { ip[j] = false; } } } } llint po[MAXA >> 1]; void divide( int n, int power ) { for( int i = 0; pr[i] <= n && i < nop; i ++ ) { if( n % pr[i] == 0 ) { int k = 0; while( n % pr[i] == 0 ) { n /= pr[i]; k ++; } po[i] = max( po[i], k * power ); } } } #define mod 1000000007 llint modpow( llint a, llint p ) { llint ret = 1LL; for( ; p; p >>= 1 ) { if( p & 1 ) ret = ret * a % mod; a = a * a % mod; } return ret; } int main() { //freopen( "F.txt", "r", stdin ); //freopen( "_F.txt", "w", stdout ); init_ip(); while( ~scanf( "%d", &n ) ) { for( int i = 0; i < n; i ++ ) { scanf( "%d", &m[i] ); } memset( po, 0, sizeof( po ) ); for( int i = 0; i < n; i ++ ) { scanf( "%d", &a[i] ); divide( a[i], m[i] ); } llint ans = 1; for( int i = 0; i < nop; i ++ ) { if( po[i] ) { //cout << pr[i] << WS << po[i] << endl; ans = ans * modpow( pr[i], po[i] ) % mod; } } cout << ans << endl; } return 0; }