Codeforces 1497E1 - Square-free division (easy version) (math theorm)

題目大意

請你將題目給你的數列進行切斷，每一個切斷的數列裡不可以有某兩值相乘是完全平方數，求最小切斷的長度

題目連結

重點觀念

• 了解完全平方數的特性
• 進行優化，不可簡單思考就開始寫入

##　分析
這題很有趣，學了一課。

我們可以知道完全平方數的特性是，每一個質因數的次方都是偶數才有辦法組成完全平方數，那現在只剩下一個問題了，我們怎樣知道哪些數字相乘會等於完全平方數呢？

此時我們可以透過完全平方數反推，只要有一個質因數的次方不是偶數就不會是完全平方數，那麼只要有另外一個數字相乘可以讓所有的質因數次方都變成偶數。

舉例： 18 = 2 * 3 * 3，此時我們的 2 的次方是奇數，那我們只要再補給他 2 就會等於 36 是個完全平方數了！
在進一步想，如果讓 18 * 8 = 144，也是完全平方數， 8 = 2 * 2 * 2，2^3 也是奇數，因此我們只要讓兩個數字相乘後每一個質因數 都是偶數，遇到這樣的情況時就可以切斷。

而我們知道奇數 + 奇數 就是偶數，因此我們只要知道當前片段有幾個質因數是奇數在紀錄就好。

現在還有一個問題要稍微避險下，18 = 2 * 3 * 3, 6 = 2 * 3，這樣是沒有滿足所有的質因數的次方都是偶數，會變成 108 = 2 * 2 * 3 * 3 * 3，因此這樣不算。

如果要讓 6 乘以另一個數字相乘必須是滿足所有的質因數的次方都是偶數，因次需要另外一個 6 來補足就變成了 36 = 2 * 2 * 3 * 3。
這裡我們得知一件事，我們除了計算哪些質因數次方是奇數外，還要讓這些奇數質因數次方相乘。

得出結論

• 把所有數字拆解質因數
• 當數字的所有質因數為奇數次方時，相乘這些奇數次方的質因數(定義 p)
• 保存 p，只要後面的數字也有另外一個 p 時就切斷數列

參考連結

E1. Square-free division (easy version) (数论、思维) by tom_bbv

心得

題目考到我了QQ，不過我認為我學習了蠻多思維，希望這些思維我都能學會並且派上用場。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 200020
using namespace std;
int t, n, k, num[MAXN]; //num 輸入題目數列用
map<int,int> mp; //紀錄每個 p，前面定義過的

int divid(int x){
    int p = 1; //紀錄此數字所有奇數次方的質因數相乘
    for(int i = 2; i*i <= x; i++){ //質因數分解
        int cnt = 0;
        while(x % i == 0){ 
            cnt++; //紀錄總共有幾次的次方
            x /= i; //約分，加速迴圈效率
        }
        if(cnt % 2 != 0) p *= i; //奇數次方的質因數相乘
    }
    return p*x; //這邊還要再乘以 x，因為前面有約分，所以 x 會是最後一個沒有被加入迴圈的質因數，回傳 p
    //x 也可以等於 1，因為 1 是質因數
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        int ans = 0; //紀錄要切幾個線段
        mp.clear(); //先將前面紀錄有哪些 p 先清除，避免干擾
        cin >> n >> k;
        for(int i = 0; i < n; i++){ //輸入題目數列
            cin >> num[i];
            int p = divid(num[i]); //質因數分解，回傳此數字所有奇數次方的質因數相乘
            if(mp.count(p)){ //如果 p 有被記錄表示，這裡會被組成完全平方數
                ans++; //這邊切線段，然後清除之前紀錄的 p
                mp.clear();
            }
            mp[p] = 1; //這次的 p 要被記錄，因為是在另一個線段
        }
        cout << ans+1 << '\n'; //最後的線段不會再被我們切到，因此這邊要 +1，加入最後一個線段
    }


    return 0;
}