1.平面上有一个圆, 圆心坐标为(0,0),半径为n. 问圆周上有多少个整点. 整点的定义即x,y坐标均为整数的点.
做题过程：思考后感觉有点难度，可能用到一些奇怪的知识，于是决定去看题解；
题解：
1.一般人都能想到x2+y2=r2这一点，但是仅想到这一点并没什么用；
2.变形：
移项得：r2-x2=y2
得y2=(r-x)(r+x)
设d=gcd((r-x),(r+x))
则设A=(r-x)/d,B=(r+x)/d
代入原式得 y2=ABd2
因为gcd(A,B)=1
所以A,B均为完全平方数
设a2=A,b2=B
可得a2+b2=2r/d
3.得到上面的式子，d很显然是2r的约数，可以枚举d；
在枚举d时，可以枚举a，算出b，若gcd(a,b)等于1，则ans++即可；
个人理解：实际上它这个最后的式子相比于最初的式子有什么优点呢？
第一个是r的次数由2次方变成了一次方，于是就可以发现原来的一个O(n)级别的算法成了根号级别的算法；
本质上是通过数学运算除去原本枚举时的无用状态；
代码：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include
View Code 2.一共有4种硬币，面值分别为c1,c2,c3,c4. 阿Q带着一些硬币去商店买东西，他带了d1枚第一种硬币，d2枚第二种硬币，d3枚第三种硬币，d4枚第四种硬币，若想买一个价值为s的东西,问阿Q有多少种付coins的方法.比如c={1,2,5,10},d={3,2,3,1},s=10,一共有4种方法:10=1+1+1+2+510=1+2+2+510=5+510=10注意,阿Q可能会去很多次商店，每次带的硬币数量和要买的东西价值可能不一样，你需要对每一次都求出方法总数。
以前做过的题目再做一遍；
题解：
1.先预处理出来f数组，f[i]表示这四种面值的钱凑成i面额有多少种方案；
2.然后利用容斥原理，对每次询问，用全部限制的方案数-限制第一种物品的方案数-限制第二种物品的方案数-限制第三种物品的方案数-限制第四种物品的方案数+限制第一，二种物品的方案数......+限制1,2,3,4物品的方案数；
累计完之后便是答案；
为什么？
以限制第一种物品为例，它需要凑成s钱数，如果使用(d[1]+1)份以上的1物品，就不被允许，因此就需要用f[s]减去使用四种硬币凑成s-(d[1]+1)*c[1]的方案数，同理减去2，3，4种硬币不符要求的方案数；
但会发现多减了，因为有类似第一种第二种物品都超过了限制的情况被减去了两次，因此要加回来......容斥原理大致就是这么个意思；
#include #include #include #include #include #include #include #include
View Code
3.[haoi2008]糖果传递
老师准备了一堆糖果, 恰好n个小朋友可以分到数目一样多的糖果. 老师要n个小朋友去拿糖果, 然后围着圆桌坐好, 第1个小朋友的左边是第n个小朋友, 其他第i个小朋友左边是第i-1个小朋友。 大家坐好后, 老师发现, 有些小朋友抢了很多的糖果, 有的小朋友只得到了一点点糖果, 甚至一颗也没有, 设第i个小朋友有ai颗糖果. 小朋友们可以选择将一些糖果给他左边的或者右边的小朋友, 通过”糖果传递”最后使得每个小朋友得到的糖果数是一样多的, 假设一颗糖果从一个小朋友传给另一个小朋友的代价是1, 问怎样传递使得所耗的总代价最小
这题训练指南上有；
题解：
排除一下多余的情况，我们可以设x[i]表示i给i-1一共a[i]个糖果，a[i]小于0表示反过来给；
于是可以列式：
A[i]+x[i+1]-x[i]=S;
n个方程，n个未知数，是否可以消元？
肯定是不行的，这是一个圈上的糖果交换，前n-1个方程一定能推出第n个方程；
而且如果能这么解出来，我们还怎么保证sum(x[i])最小；
所以肯定不行；
不过我们可以发现未知数太多，难以找到规律，尝试消元；
......
x[3]=x[2]-(A[2]-S);
x[2]=x[1]-(A[1]-S);
x[1]=x[1];
这样就可以递推用x[1]表示其他未知数；
可以这么搞：
x[1]=x[1];
x[2]=x[1]-c[2];
x[3]=x[1]-c[3];
x[4]=x[1]-c[4];
......
这样很明显看出来我们要求的答案就是数轴上一堆点，x[1]到所有点距离之和；
这样很容易看出x[1]取所有点中位数的时候答案最小；
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include
View Code 注意：我们只使用前n-1个公式即可；
给你一对数a,b，你可以任意使用(a,b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)这些向量，问你能不能拼出另一个向量(x,y)。
说明：这里的拼就是使得你选出的向量之和为(x,y)
题解：
首先这八个向量是不必都用上的，去除那些加负号后等同的向量后剩下了四个(a,b)(a,-b)(b,a)(b,-a)。
最后要组成的向量是（x，y），由向量运算法则设这样的式子：
(x,y)=A(a,b)+B(a,-b)+C(b,a)+D(b,-a);
可化成：
x=a(A+B)+b(C+D)
y=b(A-B)+a(C-D)
设x1=A+B,y1=C+D,x2=A-B,y2=C-D;
x=ax1+by1;
y=bx2+ay2;
然后我们就可以看出来了，如果A，B，C，D有解，
那么x1+x2，y1+y2都是偶数；
然后利用拓展gcd求出一组x1,y1,x2,y2，
判断一下即可；
细节上主要注意直接求出的一组解可能不符条件，但变形后就符合条件了
由于判断的是奇偶，每个方程的解最多两种情况，乘起来一共四种情况，都需要判断；
详见代码:
#include #include #include #include #include #include #include #include
View Code