2021-07-21訓練日記upc聯通數(思維)|賽博朋克(唯一分解)

A. 聯通數

題目描述

數學高手小G最近發現了一種新型的數！
他首先在草稿紙寫下任意長度的數字串kkkkkkkkkkk…(1≤k≤9)并在其中間添加加號，且相鄰兩個加號之間至少含有兩個數字k (默認數字串第一個數字前與最后一個數字后也有兩個加號)，然后對其進行求和得出一個新的數，像這樣得出的數他將其定義為 “k聯通數 ” ，
小G對于他的發現感到非常的自豪， 像數字854就能表示為77+777，因此854是7聯通數，
小G現在非常好奇， 究竟有哪些數可以是k聯通數呢？他想考驗一下你，
詢問T次，每次給定兩個數n,k，判斷 n是否為k聯通數， 如果是，輸出 YES，否則出 NO，

輸入

第一行一個整數T，表示詢問個數，
接下來T行，每行兩個整數n,k，意義如上所示，

輸出

T行，每行輸出 YES 或 NO，

樣例輸入

3
854 7
111 2
554 2

樣例輸出

YES
NO
YES

提示

通過題意可以看到：
如果n是k聯通數，那么一定可以得到 n % k == 0，反之就不是k聯通數

在n % k == 0的情況下{
如果n / k是11 111這種相加組成的，那么一定就是YES，反之就是NO
到這里就和cf一個題很相似：鏈接
該題對應題解：鏈接
如果可以由11 111這種組成就是YES，反之就是NO
}
Code:

int main() {
    ll _ = read;
    while(_ --) {
        ll n = read,k =  read;
        if(n == 0) {
            puts("NO");
            continue;
        }
        if(n % k == 0) {
            ll t = n / k;
            int flag = 0;
            for(itn i=0; i*111<=t; i++) {
                if((t - i*111) % 11 == 0) {
                    flag = 1;
                    break;
                }
            }
            if(flag) puts("YES");
            else puts("NO");
        } else puts("NO");
    }
    return 0;
}
/**
 
 
 
 
**/
 
/**************************************************************
    Problem: 20006
    Language: C++
    Result: 正確
    Time:318 ms
    Memory:17656 kb
****************************************************************/

B. 賽博朋克

題目描述

在遙遠的公元前65536世紀，β星座的焃碁星人發現了地球，他們對于該星球上碳基生物的大腦構造感到非常的好奇， 在植入了夸克級別的神經元控制器后， 他們奪取了所有生物大腦內驚人的算力，進而控制了所有的生物，
幾億年以后， 人類憑借著自己貧瘠的算力， 造出了龐大而驚人的超大規模集成電路，他們訓練的AlphaPenguin 系統經過了幾億億的和棋訓練， 已經達到了與焃碁星人相同的智力水準，
AlphaPenguin在企圖破譯焃碁星人的最高權限密碼，奪回所有生物的算力控制權時， 發現焃碁星人采用了以下的動態加密方式：

比起焃碁星人，AlphaPenguin由于沒有足夠的算力而對此感到無能為力，因此它采用了分布式計算的方法，將一小部分任務交給了你做，
具體地，你現在得到了n個數， 你需要求出這n個數中所有任意兩個數的最小公倍數的最大公因數， 并把答案回傳給AlphaPenguin，

輸入

第一行一個整數n，表示你得到的數的個數，
第二行n個整數，a1,a2,…,an表示每個數的大小，

輸出

一行，一個整數，表示你計算出的結果，

樣例輸入

【樣例1】
4
10 24 40 80
【樣例2】
10
540 648 810 648 720 540 594 864 972 648

樣例輸出

【樣例1】
40
【樣例2】
54

提示

樣例解釋
在第一個樣例中，lcm(10,24)=120,lcm(10,40)=40,lcm(10,80)=80,lcm(24,40)=120,lcm(24,80)=240,lcm(40,80)=80，gcd(120,40,80,120,240,80)=40,因此答案即為40，

首先通過提議我們可以知道，這個題讓求的是任意兩個數的lcm的gcd
根據lcm,gcd定義我們可以知道：

在這里先將求完lcm，再求gcd的結果記為x
看樣例{
4
10 24 40 80
10 == 2¹ * 3⁰ * 5¹
24 == 2³ * 3¹ * 5⁰
40 == 2³ * 3⁰ * 5¹
80 == 2⁴ * 3⁰ * 5¹
①對于2的次方數中，對答案x的貢獻一定是次小的那個次方數(2^3)
②對于3的次方數中，對答案x不會產生貢獻(因為只有一個數有三的次冪)
③對于5的次方數中，對答案x的貢獻是因子中有5且次方數最小的那個(5^1)
答案x == ①2 ^ 3 * ③5 ^ 1 == 40
所以我們可以看到，將這n個數唯一分解之后，有這個數的冪次的數量為 >= n - 1才可以
數量 == n的時候，貢獻是次小的冪次
數量 == n - 1的時候，貢獻是最小的那個冪次
這個時候對每一個質因子的次方數維護在對應的優先佇列(小根堆)里面就好啦
}
code:

typedef int itn;
ll prime[maxn],tot;
bool vis[maxn];
void getPrime() {
    memset(vis,0,sizeof(vis));
    tot = 0;
    for(int i=2; i<=maxn; i++) {
        if(!vis[i]) prime[++tot] = i;
        for(int j = 1; j <= tot && i * prime[j] <= maxn; j ++) {
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}
ll p[maxn],a[maxn],cnt;
void get(ll n) {
    cnt = 0;
    for(int i=1; prime[i] * prime[i] <= n; i++) {
        if(n % prime[i] == 0) {
            p[++cnt] = prime[i];
            a[cnt] = 0;
            while(n % prime[i] == 0) {
                a[cnt]++;
                n /= prime[i];
            }
        }
        if(n == 1) break;
    }
    if(n > 1) p[++cnt] = n,a[cnt] = 1;
}
ll num[maxn];
priority_queue <int, vector<int>, greater<int> > que[maxn];
int main() {
    getPrime();
    int n = read;
    for(int i = 1; i <= n; i ++) num[i] = read;
    for(int i = 1; i <= n; i ++) {
        get(num[i]);
        for(int j = 1; j <= cnt; j++) {
            ///vet[i].push_back({p[j],a[j]});
            que[p[j]].push(a[j]);
            ///cout<<p[j]<<' '<<a[j]<<endl;
        }
    }
    ll ans = 1LL;
    for(int i = 0; i <= maxn; i++) {
        if(que[i].size() == n - 1) {
            ll p = que[i].top();
            ans *= qPow(i,p);
        }
        else if(que[i].size() == n) {
            que[i].pop();
            ans *= qPow(i, que[i].top());
        }
    }
    cout << ans <<endl;
    return 0;
}
/**
10
540 648 810 648 720 540 594 864 972 648
 
4
10 24 40 80
 
**/
 
/**************************************************************
    Problem: 20007
    Language: C++
    Result: 正確
    Time:312 ms
    Memory:68408 kb
****************************************************************/