游客 注册 | 登录
中文 | En

3055 - 雯神与狗不得不说的故事3

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

上回说到雯神现在不怕狗了反而喜欢狗了。今天雯神走到了一个奇怪的地方，这个地方有好多狗狗，并且有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 />

题目输入

多组输入。

对于每组数据：

第一行一个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 )

题目输出

对于每组数据，输出一行，该行包含一个整数u%(10^9+7)的结果。

输入/输出样例

输入格式

3
1 1 1
1 2 3

输出格式

6

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;
}
请先登陆