Bedao Testing Contest 01 - FRAC

View as PDF
Submit solution
Points: 0.24 (partial)
Time limit: 0.4s
Memory limit: 256M
Input: stdin
Output: stdout
Authors:
ntkwan, iostream
Problem types
Allowed languages
C, C++, Pascal
Bài chỉ được chấp nhận các ngôn ngữ C, C++ và Pascal

Vào ngày hè nắng nóng, sau khi giải xong 300 bài code thiếu nhi, Muối mở game lên và chơi nhưng do hay tải game lậu nên máy Muối đã bị nhiễm virus và hiện lên thông báo yêu cầu Muối phải giải được bài toán sau đây: Cho số nguyên không âm ~n~, gọi tích ~n~ số nguyên không âm ~a_i~ là ~G~, bội chung nhỏ nhất ~n~ số nguyên không âm ~a_i~ là ~F~, hãy tính ~\frac{G}{F}~. Vì đã khá mệt sau khi giải nhiều bài, Muối cần bạn giúp.

Input

  • Dòng đầu tiên, chứa số ~n~.
  • Dòng thứ hai, chứa ~n~ số ~a_i~ ( ~a_i \le 10^7~ ).

Output

  • Một dòng chứa số nguyên duy nhất là đáp án. Nếu không có đáp án in ra ~impossible~. Dữ liệu đảm bảo đáp án không lớn hơn ~10^{18}~

Sample Input 1

3
1 2 3

Sample Output 1

1

Subtask

  • ~50\%~ số test có ~n \le 21~
  • ~50\%~ số test còn lại có ~n \le 100~

Giải thích ví dụ

Ở ví dụ, ta có: ~G~ = ~1 \times 2 \times 3 = 6~, ~F~ = ~6~ => ~\frac{G}{F}~ = ~\frac{6}{6}~ = ~1~ .

Comments

Please read the guidelines before commenting.


  • 0
    ngoccaidu2008  commented on Oct. 12, 2025, 2:37 p.m.

    hay

    #pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define __Hormer_Nguyen__ signed main()
#define int long long
#define pii pair<int,int>
#define X first
#define Y second
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
const int maxn=5+1e3;
const int N = 1e6+5;
const int MOD = 1e9+7;
const int INF = 1e18+7;
__Hormer_Nguyen__ 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    if(n==0) return cout<<"impossible",0;
    vector<int>a(n);
    int cnt0=0;
    for(int i=0;i<n;i++) 
    {
        cin>>a[i];
        if(a[i]==0)cnt0++;
    }
    if(cnt0>0) 
    {
         cout<<"impossible";
        return 0;
    }
    map<int,int> mp1,mp2;
    for(auto x:a) 
    {
        if(x>0) 
        {
            for(int i=2;i*i<=x;i++) 
            {
                if(x%i==0) 
                {
                    int cnt =0;
                    while(x%i==0) 
                    {
                        x/=i;
                        cnt++;
                    }
                    mp1[i]+=cnt;
                    mp2[i]=max(mp2[i],cnt);
                }
            }
            if(x>1) 
            {
                mp1[x]+=1;
                mp2[x]=max(mp2[x], 1LL);
            }
        }
    }
    int res =1;
    for(auto x:mp1) 
    {
        int cur=x.Y-mp2[x.X];
        for(int i=0;i<cur;i++) res*=x.X;     
    }   
    cout<<res;          
}

  • -105
    SinsAries  commented on Aug. 10, 2021, 1:50 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.