testpost

Hi! This is a testpost.

hello world

---

1114F Please, another Queries on Array? 2023.3.20

statement

支援區間乘法，區間詢問 \(φ(a_i \times a_{i+1} ... \times a_j)\)。 𝜑為歐拉函數。 \(n\le 4\times 10^5\)， \(q\le 2\times 10^5\)， \(a_i,x \le 300\)。

solution

因為 \(φ(n) = n \times \prod_{p|n}(1-\frac{1}{p})\) ，而 300 以下的質數只有 62 個，所以開一個線段樹支援一般的區間乘法和區間 bitwise or ，代表這個區間有沒有這個質數。 弄一弄就做完了 \(fpow(a,b)\) 可以預處理，應該會更快一點

diff = 2400

int n,c;
ll arr[100005],now[100005];
vector<pii> a,b;
ll work(ll goal){
    ll R = goal*n*2, L = R-n*2+1, res = 0, tot = 0;
    for (int i=1;i<=n;i++) now[i] = arr[i], tot += arr[i];
    for (pii p:a){
        ll cost = p.first, id = p.second;
        if (now[id] < goal) res += cost * (goal-now[id]), tot += (goal-now[id]), now[id] = goal;
    }
        
    if (tot < L){
        for (pii p:a){
            ll cost = p.first, id = p.second;
            ll most = c - now[id];
            if (most <= L-tot) tot += most, now[id] = c, res += cost * most;
            else res += (L-tot) * cost, now[id] += (L-tot), tot = L;
        }
    }else if (tot > R){
        for (pii p:b){
            ll cost = p.first, id = p.second;
            ll most = now[id] - goal;
            if (most <= tot-R) tot -= most, now[id] = goal, res += cost * most;
            else res += (tot-R) * cost, now[id] += (tot-R), tot = R;
        }
    }
    return res;
}

插入圖片

把圖片丟在 source/_posts/post_name/ （好像不行）

把圖片丟在 source/images

文章裡面用

![](/images/image2.png)

注意：用localhost時跑不出圖片。

deploy

本地寫好文章，打

hexo cl
hexo g
hexo d

---