我的数学果然很差劲 QAQ。。。
人蠢就要多努力。。。。再不努力就会退役好吗。。。

T1

题目描述：
我是一个傻×蒟蒻，总是被屠，最近连 xzy 都开始屠我了,55555~
我研究了一下每天屠我的人的总数，发现这样一个规律。
首先，每个人都只会屠我一次，然后就不屑于屠我了。第一天有 1 个人屠了我，第二天有 1 个人屠了我，但是从第三天开始，之前两天屠我的人会告诉他们的一个朋友（当然是没有屠过我的），让他们来屠我。结果，从某时候起，居然连外星人都不远千里来到地球开始屠我了。
作为一个傻×蒟蒻真 diaosi，我知道，如果一天被屠 X 次，则你的 RP 会上涨 X2 点。到今天为止，我已经被屠了 N 天。我想算一算这 N 天我获得了多少点 RP，但是我还得去选取数字，就拜托你了。勇敢的骚年啊快去创造奇迹！
答案对 1000000007 取模
数据范围：
对于 20% 的数据，保证有 $1≤n≤20$。
对于 50% 的数据，保证有 $1≤n≤10^5$。
对于 100% 的数据，保证有 $1≤n≤10^{15}$
题目分析：
其实是打表找规律。。。关于斐波那契数列有很多神奇的规律，不太好正着推，找到规律后可以证明的那种。。。简直了。。。
这题的规律是：$ans=f_n * f_{n+1}$
怎么证明？记 $s_n=\sum_{i=1}^n f_i^2$，则：
$s_1=f_1 * f_1=f_1 * f_2$, 这是显然的 ($f_1=f_2=1$)。
$s_2=s_1+f_2 * f_2=f_1 * f_2+f_2 * f_2=f_2 * (f_1+f_2)=f_2 * f_3$
以此类推，证明完毕。
然后就可以用矩阵快速幂快速求解了。
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
using namespace std;
#define LL long long
LL mod=1000000007,n,ans;
LL f1,f2,now;
LL a[4][4],re[4][4],kl[4][4];
LL work(LL x){
    int i,j,k;
    re[1][1]=1,re[2][2]=1;
    a[1][1]=1,a[1][2]=1,a[2][1]=1;
    while(x){
        if(x&1){
            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++){
                kl[i][j]=0;
                for(k=1;k<=2;k++)kl[i][j]+=a[k][j]*re[i][k];
                kl[i][j]%=mod;
            }
            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)re[i][j]=kl[i][j];
        }
        for(i=1;i<=2;i++)
            for(j=1;j<=2;j++){
            kl[i][j]=0;
            for(k=1;k<=2;k++)kl[i][j]+=a[i][k]*a[k][j];
            kl[i][j]%=mod;
        }
        for(i=1;i<=2;i++)
            for(j=1;j<=2;j++)a[i][j]=kl[i][j];
        x>>=1;
    }
    return (re[1][1]*re[1][2])%mod;
}
int main()
{
    freopen("crazy.in","r",stdin);
    freopen("crazy.out","w",stdout);
    scanf("%lld",&n);
    printf("%lld",work(n));
    return 0;
}

T2

题目描述：
黑了很多人今天来黑下自己。
其实每个数字都是有灵魂的。譬如说我，能被 2 整除的数字看起来都有点 2,。能被 4 整除的数字不仅 2 还一脸死相。能被 5 整除的数字看起来昨天才哭过。能被 7 整除的数字，原来就是你把 5 弄哭的！好吧，蛋疼到这里结束。
其实做数据是很累人的，不管你们信不信，反正我是信了。
每次其实我都想这么出数据。首先决定我今天的幸运数字，然后再选定若干个悲剧数字，一个数字是幸运的定义为能够整除我今天的幸运数字而且不能够整除那若干个悲剧数字，最后选定一个区间 [L,R]，将这个区间中所有的幸运的数字挑出来。我想知道，我究竟能挑出多少个幸运的数字？
Note：幸运的数字和我今天的幸运数字不是同一个东西。
数据范围：
对于 30% 的数据，保证有 $0≤n≤2$，$1≤L≤R≤10^5$。
对于 100% 的数据，保证有 $0≤n≤15$，$1≤L≤R≤10^{15}$，今天的幸运数字和悲剧数字均可用无符号 32 位整型变量存下。
题目分析：
容斥水题。
ans=能被幸运数字整除的数的个数-（能被 1 个悲剧数字和幸运数字整除的数的个数）+（能被两个悲剧数字和幸运数字整除的数的个数）-…
每一个括号就是求一下最小公倍数什么的。。。
可以用 dfs 实现。
反思：
当时为了防止爆 long long，加了个判断，如果当前最小公倍数大于 r 就直接 return。
但是还是爆了。
因为在求最小公倍数的中间过程上我是先乘，再除的。
应该先除再乘，然后开个 unsigned 就行了。
最后拿个近似暴力的 40 分。。。
唉，思维不够严谨啊。。。以后一定要考虑清楚这些问题。。。数据范围大的情况下要防止爆炸。。。
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
using namespace std;
#define LL unsigned long long
int n;LL l,r,uk[20],luk,ans;
LL gcd(LL x,LL y){
    LL r=x%y;
    while(r){x=y,y=r,r=x%y;}
    return y;
}
void dfs(int x,LL fh,LL num){
    if(num>r)return;
    if(x==n+1){ans+=fh*(r/num-(l-1)/num);return;}
    dfs(x+1,fh,num),dfs(x+1,-fh,num/gcd(num,uk[x])*uk[x]);
}
int main()
{
    freopen("lucky.in","r",stdin);
    freopen("lucky.out","w",stdout);
    scanf("%llu%d%llu%llu",&luk,&n,&l,&r);
    for(int i=1;i<=n;i++)scanf("%llu",&uk[i]);
    dfs(1,1,luk);
    printf("%llu",ans);
    return 0;
}

T3

题目描述：
众所周知，一中 2011 届信息组有许多胖子。
无奈他们体型过于巨大，于是，他们就请我来节制他们的饮食。我决定，每天喂他们吃粥，这样既可以保证营养，又可以减肥。但是，粥一旦多了，他们就觉得不爽，觉得自己长胖了，粥一旦少了，就不能让他们该题目和考试了。经过长期观察研究，最适合的粥量为 N，多一分不行，少一分不干。
悲剧的是，我只有两个勺子，而且它们的容量分别为 A 和 B。当然，装粥的那口缸和盛着刚做好的粥的锅是非常大的，你可以将它们的容量视为无穷大。每次，我只能使用一个勺子，用锅里的粥将这个勺子装满，然后倒入缸里面，或者用缸里面的粥将这个勺子倒满，然后放回锅里。对了，每天锅里的粥可以视为无穷大。我比较怕麻烦，希望知道一个最小的操作次数。
当然，他们要我节制他们若干天，所以每天的最适合粥量可能不同。但是，勺子是不会换的（囧）。
数据范围：
对于 50% 的数据，保证有 $1≤A,B,N≤105$，数据组数等于 1。
对于 100% 的数据，保证有 $1≤A,B,N≤109$，数据组数不超过 1000。
题目分析：
首先，我们要求的是使得 Ax+By=n 中 abs(x)+abs(y) 最小的情况下的 x 和 y。
怎么求？
我们知道 Ax+By=gcd(A,B) 是可以用扩欧求出来的，同时将 x 和 y 扩大 (n/gcd(A,B)) 倍可以得到在 Ax+By=n 条件下的解。然后通解可表示为 $x+b/gcd * t$和 $y-a/gcd * t$，这可以看作两条直线，一条斜率小于 0，一条大于 0，则肯定会相交。
如图所示，当 x 和 y 为一正一负的时候，abs(x)+abs(y) 就是红线代表的长度。肯定是越靠近 x 和 y 中有一个值为 0 的地方越小。当 x 和 y 同正或同负的时候，则解可以表示为 $x+y+(a-b)* t$或者 $-x-y-(a-b) * t$, 具有单调性，所以答案一定会在 x 和 y 有一个值非常逼近 0 的地方取到。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
using namespace std;
#define LL long long
LL a,b,n,ans;
LL exgcd(LL a,LL b,LL &x,LL &y){
    if(!b){x=1,y=0;return a;}
    LL re=exgcd(b,a%b,x,y),tmp=x;
    x=y,y=tmp-(a/b)*y;
    return re;
}
LL bs(LL x){if(x<0)return -x;else return x;}
int main()
{
    freopen("feed.in","r",stdin);
    freopen("feed.out","w",stdout);
    LL d,x,y,kx,ky,i,t;
    scanf("%lld%lld",&a,&b);
    d=exgcd(a,b,kx,ky);
    a/=d,b/=d;
    while(scanf("%lld",&n)!=EOF){
        if(n%d){printf("BeiJu!\n");continue;}
        x=kx*(n/d),y=ky*(n/d);ans=LLONG_MAX;
        t=-(x/b);
        for(i=t-1;i<=t+1;i++)ans=min(ans,abs(x+b*i)+abs(y-a*i));
        t=y/a;
        for(i=t-1;i<=t+1;i++)ans=min(ans,abs(x+b*i)+abs(y-a*i));
        t=(y-x)/(a+b);
        printf("%lld\n",ans);
    }
    return 0;
}

反思：
做题时陷入了一个思维误区，认为在 Ax+By=gcd(A,B) 条件下的任意 x 和 y 对应的 abs(x)+abs(y)，在 Ax+By=n 条件下都会被转化为 $(n/gcd(A,B)) * (abs(x)+abs(y))$, 所以只要求在 Ax+By=gcd(A,B) 条件下的最优解就可以通过乘以 (n/gcd(A,B)) 来得到在 Ax+By=n 条件下的最优解。
然而并非如此，因为在 Ax+By=gcd(A,B) 条件下的通解的表示方法是：$x+b/gcd * t$和 $y-a/gcd * t$。而在 Ax+By=n 条件下的通解则是 $x *(n/gcd(A,B))+b/gcd * t$和 $y *(n/gcd(A,B)-a/gcd * $才对。
而我却认为思路没有问题所以并没有测很多数据。
其实也是因为没有做出第一题有点急躁了，要记住考试的时候一定心要平静，不然容易陷入误区。

反思

1. 我最大的问题就是思维不严谨，在数学这一块就额外体现出来了，数学的题目大多有很多细节要考虑，要注意，一旦思维出现了漏洞，就连暴力分都拿不到。而且做这类问题的时候一定不能 “想当然” 的认为 “应该可以”，因为想一道题目的解法只想到了一半就是前功尽弃，只有暴力分。一定要在” 确定可以 “（虽然这个确定不一定是证明，也可以是” 大量的事实证明 “，因为是 Oi 题嘛！）的前提下才能使用想到的解法。
2. 思维不够灵活，要掌握好各种数学公式的证明，推理，多做一些题感受数学思维。
3. 不要迷信对拍，也不要迷信思路，思路检查与数据检查同样重要。当思维陷入一个完全的误区的时候，可能会有一组数据将你拯救回来。
4. 考试的时候不要紧张，哪怕做不出题目来也不要紧张。一场考试可能是水题和难题并存的，水题也可能会伪装得很好，所以” 透过现象看本质 “很关键，判断题目难度的眼光也很重要。这个眼光可能也要通过多做题来积累了。
5. 保持睡眠充足很重要。。。