题目：多组输入每组一个正整數n（n<=10^6）,求n以内与n互素的平方和

思路：先将n素数分解一下，求出所有素数因子然后求出所有与n不互质的数的平方和（容斥原理），再用1-n（利用公式（n*（n+1）*（2n+1）/6）的平方和减去这些与n不互质的平方和例如n为12，它的素数因子为2,3所以所有与n不互质的数为2,3,4,6,8，9,10其中素因子2 1标记法，二是用dfs（深度优先遍历）两种方法都会在下面代码中给出。

这里再补充说明一下dfs是如何进行容斥的以素因子2,3,5,7为例子结合代码二，如丅图