题目大多是1年前做的了，此文作为总结回忆性质的题解。

简单题较短，某些题目可能略长。

sgu101 . 无向图的欧拉路径问题。我是先把路求出来，再硬搞的方案。

sgu102.  求n的欧拉函数phi(n)， 将n分解用公式即可。

sgu103.  最短路，带有一定的动态性，但还是满足最优化子问题。

sgu104.  及其简单的DP，IOI以前的原题来着

sgu105.  div3， 因为10%3==1，故易推知答案为( n / 3 * 2 + (n % 3 > 1? 1 : 0))。

sgu106.  解线性方程， 用扩展欧几里得或者用求逆元的方法得到一组代表解，然后求通解中参数的范围即可。 特殊情况即a b中有一个或两个0， 注意答案可能会超过int32范围。

可以参考这个

sgu107.  9位数满足条件的有8个，否则嘛，只要最后9位是这8个情况中的一种就行，其余任意，故答案为7200000...，根据n控制0的个数即可。

sgu108.  自我数，直接求出所有<=n的自我数。 先将询问排序，求到对应询问的时候，记录下结果。 由于限制了空间，需要循环使用队列来计算。 因为如果当前数是k， 其产生的数将<=k+6*9= k+54，故使用长度200的循环数组存放绝对是ok的了~

sgu109.  构造题。 先将棋盘黑白染色，假设左上角是黑色的。即当前人物站在黑色的格子中。

这里先介绍n为奇数时的构造方法，n为奇数时，先让此人走奇数步，则他一定在白格子中，我们便可以将最外面一圈黑格子删掉而使得游戏可以继续。接着再让其走奇数步，则他又将出现在黑格子中（并不在最外面的一圈），于是我们可以删掉最外面这一整圈了。这是问题便 转化为n-2大小的棋盘，由于n-2还是奇数，n=1为边界条件，该问题即得到解决。

n为偶数的时候，只要先想办法走2步转化为n-1即可。

sgu110.  计算几何题， 尚未写

sgu111. & sgu112. 裸的高精度题来着，Java写起来超简单啊

sgu113. Nearly prime numbers.  和分解质因数的方法差不多

sgu114. 如果你把所有的人都放在坐标轴上，中位数就是答案。 对于城市来说，就是个加权中位数的问题而已。

sgu115. 简单的算一下就行

sgu116. 背包问题， 只是"物品"需要根据题目求一下而已。

sgu117. 模K M次剩余来着。这个题目只需要求出最小的t，满足K | t^M， 这样其余所有满足条件的解都必为t的倍数。

sgu118. 直接做即可。

sgu119.  令g = gcd(a, b, n)，则(i*(a/g)%n, i*(b/g)%n)这样的数对就是所有的答案。

sgu120.  就是个几何题

sgu121.  已知解法存在DFS树构造和Eular路构造， 尚未实现。

sgu122.  特殊图的哈密尔顿回路，每次贪心选择当前剩下度最小的点即可。 也有构造方法。

sgu123.  直接照着做即可，答案long long 可存

sgu124. 计算几何，直接射线法可。

sgu125. 搜索，朴素的剪枝即可。