有同学用了暴力居然都过了,这卡常居然能过,不公平呀,数据也太水了吧.
 不能太懒,想到一个AC的方法,如果在短时间内没有想到更简单的方法,则打.
 之后
 题目描述
 一看到这是偏数学题,就泄了气.n太大了,1000000000,而且多组数据,1000组.我就想,可以枚举x,时间复杂度约为\(O(3000)\),那么处理x的难挖指数的时间复杂度最多用\(O(10)\),没有想到高效求的方法.想来想去,并没有想到什么规律.放弃~
 之后
 正解:欧拉函数,可惜我还没学.欧拉函数可以求出对于一个x,y有多少个,和本题题意极其相似.我们发现:对于一个x,y总是成对出现(证明是显然的,若 p 与 x 互质,那么p 与 x-p 也互质.我们把 p 与 x-p 结成一对),且一对和为x;如\(x=14\),y有\(1,3,5,9,11,13\),每组和都\(=x\).于是我们可以用欧拉函数求出x的y有多少个,就可以求出难挖指数是多少,一个x时间复杂度为\(O(\log n)\),常数级别,那么整个的时间复杂度为\(O(t \sqrt{n})\),完全可以过,注意有特殊情况:x=1,x=2.
 long long ans;
 int ans=x;
 return ans;
 ans=0;
 printf("%lld\n",ans);