T1 还是比较水的，列出来式子就能发现满足平方因子整除n，
T2 居然是DP，实在是没有想到，考场上用set乱搞，然后没过样例
连续两次栽在DP上了，注意积累一下思路
T1「试除法」
根据1e14的复杂度推出来应该是$\sqrt{N}$的复杂度
勾股定理写出来方程稍作化简，得$x+y=(y^2+N^2)/N$
所以$N|y^2$而且$y\in[1,N-1]$那么x一定满足条件
T2「DP」「剪枝」「链表」
定义f[i]表示考虑到第i位且第i位是一个分界点，先不要考虑多维定义从简单的开始尝试
f[i]=f[j]+cnt*cnt $O(n^2)$
有一个很显然的剪枝，f[i]初始是i，当j从大到小枚举此时cnt*cnt已经>f[i],那么就不用跑下去了
正解是O(N\sqrt{N})的链表，维护从这一位下一个往前跳到的位置
原文：https://www.cnblogs.com/casun547/p/11664736.html