答案等于$sum_{d|(P,Q)} d imes varphi (P/d)$设$P=prod_{i=1}^t p_i^{m_i}$，$P=prod_{i=1}^t p_i^{k_i}$答案就等于$P=prod p_i^{m_i-1} imes((k_i+1)(p_i-1)+[k_i=m_i])$
只用pollard-rho分解一下质因数就可以了。
注意$Q_i$可以等于0！我没注意就又wa又re一时爽，提交了50次，只能明天交了。。。
答案等于$sum_{d|(P,Q)} d imes varphi (P/d)$设$P=prod_{i=1}^t p_i^{m_i}$，$P=prod_{i=1}^t p_i^{k_i}$答案就等于$P=prod p_i^{m_i-1} imes((k_i+1)(p_i-1)+[k_i=m_i])$
只用pollard-rho分解一下质因数就可以了。
注意$Q_i$可以等于0！我没注意就又wa又re一时爽，提交了50次，只能明天交了。。。