1009

令 a = i − j, 先枚举 i 再枚举 a

 

  化为这种模式，可以不用两层i与j循环。。。不然TLE。

即对于每个 i, 求有多少个小于它的 a 满足 gcd(i,a) = 1 且 a 是奇数.

当 i 是奇数时, 答案为. （因为a不能是偶数）当 i

是偶数时, 答案为 φ(i).（欧拉函数模板）        

注意 i = 1 时, 答案为 0.    

记个前缀和就好了, 复杂度为 O(N + T).。。。。。(因为处理前缀和是N，然后询问是写在之后的，而不是循环里，所以不是N*T，而是N+T)

 

 

 

1008

 

 此题考查大数的处理啦，因为有pow(2,1000)...

此处需要若干精度知识

大整数类是JAVA。。暂时不考虑，那就用高精度还是数组模板吧。。。