Question

C程序问题

01题目描述 Description
师傅给cww布置了道题，cww看到题目就不想写，请你帮忙了：
令f(n)=Gcd(x,y)max,1<=x<y<=n
求 ∑2n+1
k=2 f2(k)%10007
输入描述 Input Description
仅一行，一个整数 n；
输出描述 Output Description
仅一行，所求整数(%10007)；(结果必须取过模后输出)

02题目描述 Description
一天你突然醒来，发现自己被关在一个魔方格里，你很快联想到异次元杀阵里的情景，觉得有必要逃出去。所幸，身上的无线电没有坏，还可以与外界取得联系。但是由外界反馈的信息来看，你并不是处于三维世界里(准确的说是超立方体，第四维并不是时间)。幸运的是你知道了魔方格之间的距离。你物理学地很棒，通过计算魔方格之间的距离的三维关系便可以弄懂了四维的概念逃出生天，你需要通过q（q<=5W)次查询魔方格之间的距离。因为超立方体很不稳定，所以你只有1秒钟时间。
因为超立方体很神奇，就像超时空传送一样，所以这样的魔方格个数n与边数m 满足 绝对值（n-m）<=1.
输入描述 Input Description
第一行三个数n,m,q
接下来m行每行三个数a,b,c表示a到b有条长度为c的通道
接下来q行每行询问x到y的距离
输出描述 Output Description
一共q行，每行输出x到y的距离

题目描述 Description
有一个n行m列的方阵，从某个方格可以通向上下左右（如果存在）的任一方格。Alice的任务是从第一行中找一个方格开始，经过某些方格，到最后一行的某个方格结束。有k个方格已经被破坏，不能作为出发点，结束点，或者被经过。Bob想要再破坏几个点从而让Alice无法完成任务，他想知道至少要破坏几个。
输入描述 Input Description
第一行为三个整数n，m，k。 接下来k行，每行一对整数x，y，表示第x行第y列的方格已经被破坏（被破坏的方格可能重复给出）。
输出描述 Output Description
仅一行，一个非负整数，表示Bob最少需要再破坏的方格数。

这三个题把我卡住了，请您帮我看看

Answer 1

1. 假设x<y，则y至少为2Gcd(x,y)，因此Gcd(x,y)<=n/2向下取整，而且可以取到。因此f(n)=n/2向下取整。剩下的求和就简单了。

2. 等价于求一个图中任意两个顶点间的距离，可以对每个顶点跑一遍Dijkstra算法，如果太慢，可以试试稀疏图上的Johnson算法：http://www.cnblogs.com/wuyuegb2312/archive/2012/11/16/2774115.html

3. 把方阵转化为一个有向图，把出发点在第一行的边记为出发边，把到最后一行的边记为到达边，然后把这个有向图的边转为点构造一个新的有向图（有从(a,b)对应的点到(c,d)对应的点的边当且仅当b=c），每条边有容量1，然后添加源点s，s到每条出发边对应的点有一条边，容量无穷，添加终点t，每条到达边对应的点到t有一条边，容量无穷。这样通过简单的分析原问题等价于求这个新图的最小割。用最大流的算法即可。