# 112上學期第二次社內賽題解
## 四則運算
照題目做就好了

#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> de, in;

int main(){
    cin >> n;
    for(int i=0, a, b; i<n+1; i++){
        cin >> a >> b;
        de.push_back(a*b);
        in.push_back(a/(b+1));
    }
    cout << "a(x)=\n";
    for(int i=0; i<de.size()-1; i++) cout << de[i] << ' ' << n-i-1 << '\n';
    if(de.size()==1) cout << "0 0\n";
    cout << "A(x)=\n";
    for(int i=0; i<in.size(); i++) cout << in[i] << ' ' << n-i+1 << '\n';
    cout << "c 0\n";
}

## 救救牛奶糖
三層迴圈硬幹
這樣是 $O(n^3)$，但其實可以壓到 $O(n^2)$，~~但是我懶~~
可以想想要怎麼改會變成 $O(n^2)$

#include<bits/stdc++.h>
using namespace std;

int n, x, y, z;

int main(){
    cin >> n >> x >> y >> z;
    for(int i=0; 2*i<=n; i++){
        for(int j=0; 2*i+3*j<=n; j++){
            for(int k=0; 2*i+3*j+4*k<=n; k++){
                if(2*i+3*j+4*k==n) cout << i << ' ' << j << ' ' << k << ' ' << i*x+j*y+k*z << '\n';
            }
        }
    }
}

## 和乘數
[題目來源](https://atcoder.jp/contests/arc165/tasks/arc165_a?lang=ja)
$A$ 是大於等於 $2$ 的正整數
我們可以分兩部分討論
1. **$A$ 是某個質數的乘冪**
若 $A$ 為某個質數的乘冪，則可以令 $A=p^e$，其中 $p$ 為質數，$e$ 為正整數
注意到，要分成兩個以上的正整數並且這些正整數的公倍數為 $A$
即 $x_i<A$ 且 $x_i|A$
有此可知 $x_i$ 一定是 $p^k(k<e)$，如此一來 $x_i|p^{e-1}$
也就是說這些數的最小公倍數最多就是 $p^{e-1}$
因此這樣的 $A$ 不是和乘數
2. **$A$ 不是某個質數的乘冪**
若是如此，則 $A$ 一定存在相異質因數 $p, q$ $(p\not=q)$
令 $k=A-\frac{A}{p}-\frac{A}{q}(\ge A-\frac{A}{2}-\frac{A}{3}=\frac{A}{6}>0)$
則我們一定能將 $A$ 分成 $k+2$ 個數
$(x_1, x_2, \cdots, x_k, x_{k+1}, x_{k+2})=(1, 1, \cdots, 1, \frac{A}{p}, \frac{A}{q})$
因此這樣的 $A$ 是和乘數

得知了這樣的結果，我們就可以簡單的去看每個 $A$ 是不是某個質數的乘冪（即是否有兩個以上的相異質因數），用 $O(\sqrt{A})$ 去做類似質因數分解的事就好了
總時間複雜度 $O(N\sqrt{A})$

#include<bits/stdc++.h>
using namespace std;

int n, a;
long long ans=0; // 記得開 long long

int main(){
    cin >> n;
    while(n--){
        cin >> a;
        int tmp=a;
        for(int i=2; i<=sqrt(a); i++){
            if(tmp%i==0){
                while(tmp%i==0) tmp/=i;
                if(tmp!=1) ans+=a; // 把一個質因數全部去掉後還有其他質因數
                break;
            }
        }
    }
    cout << ans;
}

## 好大的黑板
令 $f(x)$ 為 $x$ 可以得到最大的乘積
則我們可以寫出遞迴式
\begin{cases}
f(1)=1 \\
f(x)=\max\{x, f(\lfloor\frac{x}{2}\rfloor)f(\lceil\frac{x}{2}\rceil)\}, x\ge 2
\end{cases}
而再觀察一下則會發現
當 $x\le 4$ 時，$f(x)=x$
當 $x\ge 5$ 時
$f(\lfloor\frac{x}{2}\rfloor)f(\lceil\frac{x}{2}\rceil)\ge \lfloor\frac{x}{2}\rfloor\lceil\frac{x}{2}\rceil\ge \frac{x-1}{2}\cdot\frac{x}{2}=\frac{x-1}{4}\cdot x\ge x$
因此 $f(x)=f(\lfloor\frac{x}{2}\rfloor)f(\lceil\frac{x}{2}\rceil)$
所以整理一下可以得到
\begin{cases}
f(x)=x, x\le 4 \\
f(x)=f(\lfloor\frac{x}{2}\rfloor)f(\lceil\frac{x}{2}\rceil), x\ge 5
\end{cases}
然後再做遞迴就好了
不過這題數字很大，可能會一直算到重覆的數字，那就會 TLE
我們可以先把已經算過的數字存起來，之後再碰到它就可以直接用（~~絕對不是dp~~）
C++ 用 map，python 用 dictionary

#include<bits/stdc++.h>
using namespace std;

long long x;
const int MOD=998244353;
unordered_map<long long, long long> memo;

long long slv(long long a){
    if(memo.count(a)) return memo[a];
    if(a<=4) return memo[a]=a;
    return memo[a]=slv(a/2)*slv((a+1)/2)%MOD;
}

int main(){
    cin >> x;
    cout << slv(x);
}