NO.1
Description
我们知道，从区间[L,H]（L和H为整数）中选取N个整数，总共有(H-L+1)^N种方案。小z很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的N个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小z会告诉你一个整数K，你需要回答他最大公约数刚好为K的选取方案有多少个。由于方案数较大，你只需要输出其除以1000000007的余数即可。
Input
输入一行，包含4个空格分开的正整数，依次为N，K，L和H。
Output
输出一个整数，为所求方案数。
Sample Input
2 2 2 4
Sample Output
3
HINT
样例解释
所有可能的选择方案：(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)
其中最大公约数等于2的只有3组：(2, 2), (2, 4), (4, 2)
对于100%的数据，1≤N,K≤10^9，1≤L≤H≤10^9，H-L≤10^5
思路：容斥原理+快速幂
设g[i]表示以k*i为最小公约数的选数方案
那么对于当前的g[i]怎么求呢？
首先对于每一个i记一个left表示a/(k*i),right表示b/(k*i)
其实不算最大公约数大于k*i的情况下，就等于(right-left+1)^n-(right-left+1)，其实这个题目上也有说明。。。用快速幂求即可
那么当前g[k*i]的真正答案就等于g[i]-g[i*2]-g[i*3]……g[k*i] (k*i<=maxn)
代码：
#include<cstdio>
#include<iostream>
using namespace std;
const int mo=1000000007;
const int maxn=100000;
int n,k,a,b,l,r,g[200020];
int ksm(int x,int k)
{
int r=1;
while (k)
{
if (k&1) r=(1LL*r*x)% mo;
k>>=1;
x=(1LL*x*x)% mo;
}
return r;
}
int main()
{
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
scanf("%d%d%d%d",&n,&k,&a,&b);
l=a/k; r=b/k; if (a%k) l++;
for (int i=maxn;i>=1;i--)
{
int left=l/i,right=r/i;
if (l%i) left++;
if (l<=r)
{
g[i]=ksm(right-left+1,n);
g[i]=(g[i]-(right-left+1)+mo)%mo;
for (int j=i*2;j<=maxn;j+=i) g[i]=(g[i]-g[j]+mo)% mo;
}
}
if (l==1) g[1]=(g[1]+1)%mo;
printf("%d",g[1]);
return 0;
}NO.2
Description
小H是个数学天才，在空闲的时候他喜欢发明各种各样的函数来自娱自乐。再过不久就是小H的同学，小小H的生日了。小H决定将自己刚刚发明的第19911026号函数当作生日礼物送给小小H，并把它命名为H函数。
其中H函数是这样定义的：H[A,B,C,D(x)] = (A * B^x + C) mod D。 在生日party上，小H将自己精心构想的礼物送上。同样精通数学的小小H对H函数自然非常感兴趣，以至于把其他礼物冷落一旁，专心研究H函数。 她想 如果给定一个正整数m，那么可以用F(A, B, C, D) 表示 H[A,B,C,D(x)]在 [1,m]取最小值时的x（x为正整数，且数据保证x值唯一） 善于思考的小小H很快想到一个问题来考考参加party的朋友们。 即给定n, m, {An}, {Bn}, {Cn}, {Dn}，求出所有的F(Ai, Bi, Ci, Di)。
追求完美的小小H觉得答案念起来不够好听，为了能达到朗朗上口的效果，她偷偷修改了数据来满足F(Ai, Bi, Ci, Di) ≤ F(Ai+1, Bi+1, Ci+1, Di+1)。
Input
第1行包含2个正整数n, m。
第2 ~ n + 1行每行包含4个非负整数Ai, Bi, Ci, Di。
Output
输出文件包含n行，第i + 1行为一个整数，表示F(Ai, Bi, Ci, Di)。
保证F(Ai, Bi, Ci, Di) ≤ F(Ai+1, Bi+1, Ci+1, Di+1)。
Sample Input
3 5
373911025 1525760443 652804587 1767005941
120055457 159868670 59429374 196292251
1200581 955324 141748 2705431
Sample Output
1
2
4
Hint
温馨提示：在F(Ai+1,Bi+1,Ci+1,Di+1)中，（i+1）为下标 30%的数据满足：1 ≤ n, m ≤ 1000 60%的数据满足：1 ≤ n, m ≤ 10000 100%的数据满足： 1 ≤ n, m ≤ 100000，0
#include<cstdio>
#include<iostream>
using namespace std;
long long n,m,a[100001],b[100001],c[100001],d[100001],ans[100001];
long long ksm(long x,long y,long long z)
{
long long r=x,k=1;
while (y>0)
{
if (y&1==1) k=(k*r)%z;
y=y>>1;
r=(r*r)%z;
}
return k;
}
void doit(long long l,long long r,long head,long long tail)
{
if (l>r) return;
long long mid,min1,x,y,w;
w=0;
y=head;
mid=(l+r)/2;
x=ksm(b[mid],head-1,d[mid]);
min1=d[mid];
for (long long i=head;i<=tail;i++)
{
w=(((((a[mid]*x)%d[mid])*b[mid])%d[mid])+c[mid])%d[mid];
if (w<min1)
{
min1=w;
y=i;
}
x=(x*b[mid])%d[mid];
}
ans[mid]=y;
doit(l,mid-1,head,y);
doit(mid+1,r,y,tail);
}
int main()
{
scanf("%d%d",&n,&m);
for (long long i=1;i<=n;i++) scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
doit(1,n,1,m);
for (long long i=1;i<=n;i++) printf("%d
",ans[i]);
}NO.3
Description
Alice总是会提出很多奇怪的问题，一天他让他的朋友Bob跟他一起研究一个奇怪的问题。问题是：[A,B]中有多少个数满足组成这个数的数字之和为S，另一个问题是[A,B]内满足这一要求最小的数是哪个？
编程帮Bob解决这个问题。
Input
输入包含三个整数A,B和S(1<=A<=B<10^15,1<=S<=135)。
Output
第一行输出一个整数表示满足条件的数的个数；
第二行输出最小的满足条件的数。
输入文件保证至少存在一个数。
Sample Input
输入1：
1 9 5
输入2：
1 100 10
输入3：
11111 99999 24
Sample Output
输出1：
1
5
输出2：
9
19
输出3：
5445
11499
思路：数位dp
设f[i][j][0/1][0/1]表示前i位，和为j，第一个0/1表示是否等于(0)或大于a(1)，第二个0/1表示是否等于(0)或小于b(1)
四重循环枚举
对于每一个k和l，我们可以得出下一位枚举的范围
对于新加后的数，求出相应的k和l，进行转移
这样第一个问题就解决了
那么求最小值，我们还可以定义一个与上面差不多的方程g[i][j][0/1][0/1]
这样可以用同样的时间做两件事
最后的方案数=f[len+1][s][0][0]+f[len+1][s][0][1]+f[len+1][s][1][0]+f[len+1][s][1][1]
最小值=min(min(g[len+1][s][0][0],g[len+1][s][0][1]),min(g[len+1][s][1][0],g[len+1][s][1][1]))
代码：
uses math;
var a,b:int64;
i,j,k,l,s,z,len,l1,l2,k2,r1:longint;
x,y:array[0..16]of integer;
f,g:array[0..16,0..136,0..1,0..1]of int64;
procedure init;
var i:longint;
s1:string;
begin
readln(a,b,s);
str(b,s1);
len:=length(s1);
for i:=1 to len do y[i]:=ord(s1[i])-48;
str(a,s1);
while (length(s1)<len) do s1:='0'+s1;
for i:=1 to len do x[i]:=ord(s1[i])-48;
fillchar(g,sizeof(g),127);
f[1,0,0,0]:=1;
g[1,0,0,0]:=0;
end;
begin
init;
for i:=1 to len do
for j:=0 to s do
for k:=0 to 1 do
for l:=0 to 1 do
if f[i,j,k,l]>0 then
begin
if k=0 then l1:=x[i] else l1:=0;
if l=0 then r1:=y[i] else r1:=9;
for z:=l1 to r1 do
if (j+z<=s) then
begin
if z>x[i] then k2:=1 else k2:=k;
if z<y[i] then l2:=1 else l2:=l;
inc(f[i+1,j+z,k2,l2],f[i,j,k,l]);
if (g[i,j,k,l]*10+z)<g[i+1,j+z,k2,l2] then g[i+1,j+z,k2,l2]:=g[i,j,k,l]*10+z;
end;
end;
writeln(f[len+1,s,0,0]+f[len+1,s,0,1]+f[len+1,s,1,0]+f[len+1,s,1,1]);
writeln(min(min(min(g[len+1,s,0,0],g[len+1,s,0,1]),g[len+1,s,1,0]),g[len+1,s,1,1]));
end.
NO.4
Description
Alice又想到一个游戏：N个数每个数都在0到9之间，可以对每一个数进行加1操作，但这个加1比较特别，0-8加1后会相应变成1-9，但9加1后会变成0，给出N个数，进行M次操作，每次操作都会给出两个整数A和B(1<=A<=B<=N)，要求输出第A个数到第B个数的和，然后把A到B之间的每一个数进行一次加1操作。
你能帮助Alice吗？
Input
输入文件第一行包含两个整数N和M(1<=N<=250000，1<=M<=100000)；
第二行N个数字，每个数字都在0到9之间，中间没有空格，表示初始值。
接下来M行，每行包含两个整数A和B(1<=A<=B<=N)
Output
输出M行，每行表示对应区间的和，注意是先计算后操作。
Sample Input
输入1：
4 3
1234
1 4
1 4
1 4
输入2：
4 4
1234
1 1
1 2
1 3
1 4
输入3：
7 5
9081337
1 3
3 7
1 3
3 7
1 3
Sample Output
输出1：
10
14
18
输出2：
1
4
9
16
输出3：
17
23
1
19
5
思路：线段树
我们可以用tree[i][j]记录节点i拥有j数量的值
每次直接查询
再码个区间修改就好了
代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#define N 250010
using namespace std;
char c[N];
int n,m;
int t[N<<2],tree[N<<2][10];
void ps(int x)
{
for(int i=0;i<10;++i) tree[x][i]=tree[x<<1][i]+tree[x<<1|1][i];
}
int sum(int x)
{
int ans=0;
for(int i=1;i<10;++i) ans+=i*tree[x][i];
return ans;
}
void rev(int* x,int k)
{
if(k>10) k%=10;
static int v[10];
memcpy(v,x+(10-k),k<<2);
memmove(x+k,x,(10-k)<<2);
memcpy(x,v,k<<2);
}
void pd(int m,int x)
{
if(t[x])
{
t[x<<1]+=t[x];
t[x<<1|1]+=t[x];
rev(tree[x<<1],t[x]);
rev(tree[x<<1|1],t[x]);
t[x]=0;
}
}
void build(int l,int r,int x)
{
if(l==r){ tree[x][c[l]-'0']++; return; }
int mid=l+r>>1;
build(l,mid,x<<1);
build(mid+1,r,x<<1|1);
ps(x);
}
void plu(int l,int r,int x,int head,int tail)
{
if(head<=l&&r<=tail)
{
t[x]++; rev(tree[x],1); return;
}
int mid=l+r>>1; pd(r-l+1,x);
if(head<=mid) plu(l,mid,x<<1,head,tail);
if(mid<tail) plu(mid+1,r,x<<1|1,head,tail);
ps(x);
}
int query(int l,int r,int x,int head,int tail)
{
if(head<=l&&r<=tail) return sum(x);
int mid=l+r>>1,ans=0;
pd(r-l+1,x);
if(head<=mid) ans+=query(l,mid,x<<1,head,tail);
if(mid<tail) ans+=query(mid+1,r,x<<1|1,head,tail);
return ans;
}
int main()
{
scanf("%d%d%s",&n,&m,c+1);
build(1,n,1);
for(int a,b,i=0;i<m;++i)
{
scanf("%d%d",&a,&b);
printf("%d
",query(1,n,1,a,b));
plu(1,n,1,a,b);
}
}