题面：
https://files-cdn.cnblogs.com/files/yzhang-rp-inf/P13.gif
https://files-cdn.cnblogs.com/files/yzhang-rp-inf/P23.gif
https://files-cdn.cnblogs.com/files/yzhang-rp-inf/P33.gif
https://files-cdn.cnblogs.com/files/yzhang-rp-inf/P43.gif
题解：
T1:
算法1：暴力
算法2：记录每个区间的gcd，从前一个转移过来，用hash统计答案。
期望得分：50pts
算法3：我们注意到对于左端点为l的所有区间，gcd的取值只有log个（每次gcd变小都至少会折半），所以总的不同的gcd（l，r）的取值个数只有nlog个，于是我们有两种解法
1：考虑线段树，每个节点维护区间上的gcd，在线段树上不断二分，并统计答案。（或用rmq）
2：从左往右一次计算，用map或vector合并相同的项
以上两种算法的复杂度均为nlog^2
#include <bits/stdc++.h>
using namespace std;
map<long long,long long>mem[2],ans;
map<long long,long long>::iterator it;
main(){
freopen("gcd.in","r",stdin);
freopen("gcd.out","w",stdout);
long long n,a,b=0;
scanf("%lld",&n);
while(n--){
b^=1;
scanf("%lld",&a);
mem[b].clear();
for(it=mem[b^1].begin();it!=mem[b^1].end();it++){
long long y=__gcd(a,it->first);
mem[b][y]+=it->second;
ans[y]+=it->second;
}
mem[b][a]++;
ans[a]++;
}
scanf("%lld",&n);
while(n--){scanf("%lld",&a);printf("%lld\n",ans[a]);}
return 0;
}
T2：
算法0:输出n=1的答案
期望得分：5
算法1：暴力枚举1到10^n所有数，判断是否满足
时间复杂度：10^n*n 期望得分：15-20（打表n=8）
算法2：考虑数位dp，f[i][j]表示第i位为j的方案数，统计答案
时间复杂度：nlogn 期望得分：50
算法3：我们接着算法2来考虑，有一位比上一位要大，等同于加上若干个1，于是可以把这道题变成以下的内容：
f[0]=0 f[i]=f[i-1]10+1 a[0]+a[1]+...+a[n]=9 求sigma a[i]f[i]
珂以证明每一个满足上式的a数组的解与一个这样的数一一对应
我们单独考虑每一个f[i]对答案的贡献，可以发现为c(n+9,8)
时间复杂度：n 期望得分：70
算法4：算法3的瓶颈在于求f 的和，我们发现只要求答案模19260817，而19260817也是f数组的一个循环节，统计一下循环节个数就可以了。
时间复杂度：logn 期望得分：100
#include<bits/stdc++.h>
#define mo 19260817
using namespace std;
string st;
long long p,q,ansn;
long long po(long long x,long long y){
long long z=1;
while (y){if (y&1) z=(z*x)%mo;x=(x*x)%mo;y/=2;}
return z;
}
long long c(long long x,long long y){
long long sum=1;
for (int i=1;i<=8;i++)sum=((sum*(x-i+1))%mo)*po(i,mo-2)%mo;
return sum;
}
int main(){
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
cin>>st;
int l=st.length();
for (int i=0;i<l;i++){p=p*10+st[i]-'0';q=(q*10+p/mo)%mo;p%=mo;}
for (long long i=1,j=0;i<=mo;i++){j=(j*10+1)%mo;ansn=(ansn+j)%mo;}
ansn=(ansn*q)%mo;
for (long long i=1,j=0;i<=p;i++){j=(j*10+1)%mo;ansn=(ansn+j)%mo;}
cout<<(ansn*c(p+9+mo,8))%mo<<endl;
return 0;
}
T3:
结论题qaq
连接(0,2)(1,0),(0,4)(3,0)...以此类推，可以发现只有第一行和最后一行没有填满，连接(1,0)(0,n)和(n-1,0)(n,n)即可。
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
cin>>n;
cout<<n+1<<endl;
int x=1,y=2;
while (y<n*2){
if (x>n) printf("%d %d ",n,x-n);else printf("%d %d ",x,0);
if (y>n) printf("%d %d\n",y-n,n);else printf("%d %d\n",0,y);
x+=2;y+=2;
}
printf("%d %d %d %d\n",0,0,n,1);
printf("%d %d %d %d\n",0,n,n,n-1);
return 0;
}