2287 . 奇異果的魔法咒語
TopCoder
Tags
Description
奇異果是個大魔法師，他每天都致力於尋找新的魔法並且拿它來打爆水果王國的人民。
今天奇異果找到了一個叢林之神的咒語，為了使用咒語，他必須先施放一些詠唱。咒語旁邊有一個魔法書，上面寫著每個可使用的詠唱的魔力值。已知一個咒語是有效的當且僅當每個詠唱最多只施放一次，並且所有有施放的詠唱的魔力值的最大公因數是 $1$。詠唱的施放順序沒有影響。
奇異果已經選好了一個有效的咒語，不幸的是，他在施放的時候不小心遺漏了其中一個詠唱。更不幸的是，因為少了這個詠唱，他施放的是一個無效咒語。叢林之神非常生氣，他給了奇異果了一大堆 $ADA$ 作業作為咒語無效的懲罰。更具體的說，假設原本奇異果選擇的咒語裡面的魔力值的總和是 $A$，他實際施放的咒語的魔力值的總和是 $B$，那麼叢林之神會給奇異果 $A \times B$ 單位的 $ADA$ 作業。
芒果很好奇奇異果會獲得多少的 $ADA$ 作業，於是他找到了你，請你幫他算出，對於所有奇異果選擇的有效咒語以及他實際施放的無效咒語中，叢林之神會給他多少單位的 $ADA$ 作業。為了方便起見，你只要回答這些數字的總和 $mod \ 998244353$ 就好了。
喔對了，由於魔法書實在是太巨大了，奇異果已經整理好了一個列表，上面有每種魔力值的詠唱分別有幾個。
Input Format
第一行會有一個整數 $n$，代表奇異果整理的列表上不同魔力值的詠唱總共有幾種。
接下來的 $n$ 行，每行會有兩個整數 $a_i$, $b_i$，分別代表有 $b_i$ 個魔力值為 $a_i$ 的詠唱
對於所有測資，保證 $n \leq 10^ 5 $，$1 \leq a_i \leq 10^ 5 $，所有 $a_i$ 皆不相同，$1 \leq b_i < 998244353$
Output Format
輸出叢林之神給他的 $ADA$ 作業單位總和 $mod \ 998244353$
Sample Input 1
3
2 1
3 1
5 1
Sample Input 2:
4
2 2
3 1
6 3
10 2
Sample Output 1
138
Sample Output 2:
81320
Hints
範測一解釋：所有的可能性是
1. A = 3 + 5, B = 3
2. A = 3 + 5, B = 5
3. A = 2 + 3, B = 2
4. A = 2 + 3, B = 3
5. A = 2 + 5, B = 2
6. A = 2 + 5, B = 5
因此輸出是 8*3 + 8*5 + 5*2 + 5*3 + 7*2 + 7*5 = 138
Problem Source
CF 1436 F 改
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 2~12 | $\sum b_i \leq 18$ | 8 |
| 3 | 2~12, 43~55 | $n \leq 18$ | 11 |
| 4 | 2~12, 32~42 | $\sum b_i \leq 1200$ | 26 |
| 5 | 2~21, 32~55 | $n \leq 1200$ | 19 |
| 6 | 0~55 | 無其他限制 | 36 |