回复 @Go灬Fire :
Orz

回复 @Ezoi_HelenKeller :
终于再有人写董大神的这一道题了

太轻视了，被运算顺序搞跪了
先是ans*=(x-1)/x，先算(x-1)/x，后相乘
改成ans=ans*(x-1)/x，结果先算ans*(x-1)，一个大数爆unsigned long long了
怒跪

直接Dinic就过了......

谁能证明一下
\[ \sum_{1<=i,j<=n'and'gcd(i,j)=1}^{} {i*j} = \sum_{i=1}^{n} {i*i*phi(i)}\]

尼克搞到大象冰棍再也不用费劲做成小冰棍卖了...直接送给朱迪~收获一堆卡车的礼物2333333333

回复 @～殘觷～ :
听kp说过。

回复 @～殘觷～ :
没听说过

回复 @若连自己也无��相信，那指望谁能信 :
你知道什么叫做tb_kp流吗?

@Go灬Fire :
@～殘觷～ :
且看真假美猴王

回复 @Mike is Fool :
可以证明phi（T）= sigma ( d | T )u( T / d )* d

最小割

线性筛，隐式莫反（构造f函数的时候用的），分块，O(n)预处理，O(sqrt(n))查询
其中定义f(x)=(d|x)d*miu[x/d]，不难证明f函数的积性，之后有假设1<=i,j<=n，ans=(1<=x<=n)(n/x)*(n/x)*f(x)（莫反的枚举变量交换一下），询问分块就好了。
不难证明，F(x)=(d|x)f(x)=x（莫比乌斯反演公式可证）
所以也可以杜教筛求f函数的前缀和，每次询问O(n^(2/3))，预处理O(n^(2/3))。
这真是智障，我用莫比乌斯函数求出来了欧拉函数- -

回复 @～殘觷～ :
%%%%%%%%%%%%%%%%%

喜闻乐见，板子写错了还能A题QAQ。记得特判，第一问答案为1时输出两个n

在Linux下如果不强转貌似不会转，然后就WTE了