NOIP 模拟题
By liu_runda
题目名称 数 论 题
源程序文件名 number.cpp theory.cpp problem.cpp
输入文件名 number.in theory.in problem.in
输出文件名 number.out theory.out problem.out
每个测试点时限 1s 1s 1s
内存限制 512MB 512MB 512MB
测试点数目 10 10 20
每个测试点分值 10 10 5
是否打开O2 优化 否 否 否
数(number)
【题目描述】
给出n 个正整数,分别判断每个正整数是不是质数.
【输入格式】
第一行一个整数n 表示正整数的数目. 接下来n 行,第i+1 行一个整数ai.
【输出格式】
n 行,对于第i 行,如果ai 是质数,输出一行”YES”(不含引号),否则输出一行”NO”(不含引号).
【样例输入】
5
1
2
3
4
5
【样例输出】
NO
YES
YES
NO
YES
【数据范围】
对于10%的数据,n=1
对于50%的数据,1<=ai<=10^5
对于100%的数据,1<=n<=100,1<=ai<=10^9
论(theory)
【题目描述】
给出一个正整数n,求gcd(1,n)+gcd(2,n)+gcd(3,n)+...+gcd(n,n),即1 到n 每个数和n 的最大
公约数之和.
gcd(a,b)表示a 和b 的最大公约数,即一个最大的整数x 使得x 既是a 的约数.也是b 的约
数.
【输入格式】
一行一个整数n
【输出格式】
一行一个整数ans,表示答案
【样例输入】
11
【样例输出】
21
【数据范围】
对于30%的数据,n<=100
对于60%的数据,n<=1000000
对于80%的数据,n<=10000000
对于100%的数据,n<=100000000
题(problem)
【题目描述】
你在平面直角坐标系上.
你一开始位于(0,0).
每次可以在上/下/左/右四个方向中选一个走一步.
即:从(x,y)走到(x,y+1),(x,y-1),(x-1,y),(x+1,y)四个位置中的其中一个.
允许你走的步数已经确定为n.现在你想走n 步之后回到(0,0).但这太简单了.你希望知道
有多少种不同的方案能够使你在n 步之后回到(0,0).当且仅当两种方案至少有一步走的方向
不同,这两种方案被认为是不同的.
答案可能很大所以只需要输出答案对10^9+7 取模后的结果.(10^9+7=1000000007,1 和7
之间有8 个0)
这还是太简单了,所以你给能够到达的格点加上了一些限制.一共有三种限制,加上没有
限制的情况,一共有四种情况,用0,1,2,3 标号:
0.没有任何限制,可以到达坐标系上所有的点,即能到达的点集为{(x,y)|x,y 为整数}
1.只允许到达x 轴非负半轴上的点.即能到达的点集为{(x,y)|x 为非负数,y=0}
2.只允许到达坐标轴上的点.即能到达的点集为{(x,y)|x=0 或y=0}
3.只允许到达x 轴非负半轴上的点,y 轴非负半轴上的点以及第1 象限的点.即能到达的点
集为{(x,y)|x>=0,y>=0}
【输入格式】
一行两个整数(空格隔开)n 和typ,分别表示你必须恰好走的步数和限制的种类.typ 的含
义见【题目描述】.
【输出格式】
一行一个整数ans,表示不同的方案数对10^9+7 取模后的结果.
【样例输入0】
100 0
【样例输出0】
383726909
【样例输入1】
100 1
【样例输出1】
265470434
【样例输入2】
100 2
【样例输出2】
376611634
【样例输入3】
100 3
【样例输出3】
627595255
【数据范围】
10%的数据,typ=0,n<=100
10%的数据,typ=0,n<=1000
5%的数据, typ=0,n<=100000
10%的数据,typ=1,n<=100
10%的数据,typ=1,n<=1000
5%的数据, typ=1,n<=100000
10%的数据,typ=2,n<=100
15%的数据,typ=2,n<=1000
10%的数据,typ=3,n<=100
10%的数据,typ=3,n<=1000
5%的数据, typ=3,n<=100000
以上11 部分数据没有交集.
100%的数据,保证n 为偶数,2<=n<=100000,0<=typ<=3.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))
#define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))
#define Ii inline int
#define Iv inline void
#define Il inline long long
#define Ib inline bool
#define re register
#define ll long long
#define D_e_Line printf("\n-------------\n")
#define D_e(x) printf("\n______%d_______\n",x)
#define Pause system("pause")
using namespace std;
Ii read(){
int s=,f=;char c;
for(c=getchar();c>''||c<'';c=getchar())if(c=='-')f=-;
while(c>=''&&c<='')s=s*+(c^''),c=getchar();
return s*f;
}
Iv print(int x){
if(x<)putchar('-'),x=-x;
if(x>)print(x/);
putchar(x%^'');
}
const int mod=;
ll cat[];
Il Pow(ll a,ll b){
ll s=;
a%=mod,b%=mod;
while(b){
if(b&)s=s*a%mod;
a=a*a%mod,b>>=;
}
//D_e(s%mod);
return s%mod;
}
Il Smul(ll a,ll b){
ll s=;
a%=mod,b%=mod;
while(b){
if(b&)s=(s+a)%mod;
a=(a+a)%mod,b>>=;
}
return s%mod;
}
Iv Catalan(int &x){
x>>=,
cat[]=,cat[]=;
R(i,,x){
cat[i]=Smul(Smul(cat[i-],*i-)%mod,Pow(i+,mod-))%mod;
//D_e(cat[i])
//cout<<cat[i]<<endl;
}
}
Iv Work(int &n){
if(n==){putchar('');return;}
Catalan(n);
//printf("%d\n",(cat[n+1]%mod+mod)%mod-(cat[n]%mod+mod)%mod);
printf("%d",(cat[n]%mod+mod)%mod);
}
int anss[]={,,,,,,,,,};
#define ON_JUDGE
int main(){
#ifdef ON_JUDGE
freopen("problem.in","r",stdin),freopen("problem.out","w",stdout);
#endif
int n=read();
int opt=read();
if(opt==){
if(n==){
printf("");return ;
}
printf("%d\n",anss[n-]);return ;
}
Work(n);
return ;
}
/*
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
9694845
35357670
129644790
477638700 1
2
10
70
588
5544
56628
613470
6952660
81662152 */
problem_my_CreatOnContest.cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))
#define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))
#define Ii inline int
#define Iv inline void
#define Il inline long long
#define Ib inline bool
#define re register
#define ll long long
#define D_e_Line printf("\n-------------\n");
#define D_e(x) printf("\n______%d_______\n",x)
#define Pause system("pause")
using namespace std;
Ii read(){
int s=,f=;char c;
for(c=getchar();c>''||c<'';c=getchar())if(c=='-')f=-;
while(c>=''&&c<='')s=s*+(c^''),c=getchar();
return s*f;
}
Ii gcd(int a,int b){
while(b^=a^=b^=a%=b);return a;
}
Iv print(ll x){
if(x<)putchar('-'),x=-x;
if(x>)print(x/);
putchar(x%^'');
}
#define ON_JUDGE
int main(){
#ifdef ON_JUDGE
freopen("theory.in","r",stdin),freopen("theory.out","w",stdout);
#endif
//cout<<sizeof(ans)/4<<endl;
int n=read();
ll ans=;
R(i,,n)
ans+=gcd(i,n);
print(ans);
return ;
}
theory_my_CreatOnContest
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))
#define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))
#define Ii inline int
#define Iv inline void
#define Il inline long long
#define Ib inline bool
#define re register
#define ll long long
#define Cmax(a,b) ((a)=(a)>(b)?(a):(b))
#define D_e_Line printf("\n-------------\n");
#define D_e(x) printf("\n______%d_______\n",x)
#define Pause system("pause")
using namespace std;
Ii read(){
int s=,f=;char c;
for(c=getchar();c>''||c<'';c=getchar())if(c=='-')f=-;
while(c>=''&&c<='')s=s*+(c^''),c=getchar();
return s*f;
}
Iv print(ll x){
if(x<)putchar('-'),x=-x;
if(x>)print(x/);
putchar(x%^'');
}
Ii Phi(int x){
int sum=x;
for(re int i=;i*i<=x;++i)
if(x%i==){
sum-=sum/i;
while(x%i==)x/=i;
}
return x!=?sum-sum/x:sum;
}
Il Cal(int d,int n){
return (ll)Phi(n/d)*d;
}
int main(){
freopen("theory.in","r",stdin),freopen("theory.out","w",stdout);
int n=read();
ll ans=;
for(re int i=;i*i<=n;++i)
if(n%i==){
ans+=Cal(i,n);
if(i*i<n)
ans+=Cal(n/i,n);
}
print(ans);
return ;
}
theory_AC.cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))
#define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))
#define Ii inline int
#define Iv inline void
#define Il inline long long
#define Ib inline bool
#define re register
#define ll long long
#define Cmax(a,b) ((a)=(a)>(b)?(a):(b))
#define D_e_Line printf("\n-------------\n");
#define D_e(x) printf("\n______%d_______\n",x)
#define Pause system("pause")
using namespace std;
const int N=;
const int mod=;
Il read(){
ll s=,f=;char c;
for(c=getchar();c>''||c<'';c=getchar())if(c=='-')f=-;
while(c>=''&&c<='')s=s*+(c^''),c=getchar();
return s*f;
}
Iv print(ll x){
if(x<)putchar('-'),x=-x;
if(x>)print(x/);
putchar(x%^'');
}
int fac[N],invfac[N];
Ii C(int n,int m){
if(n<m)return ;
return (ll)fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
Ii Pow(int a,int b){
int s=;
a%=mod,b%=mod;
while(b){
if(b&)s=(ll)s*a%mod;
a=(ll)a*a%mod,b>>=;
}
return s%mod;
}
Ii Catalan(int n){
return (ll)C(n<<,n)*Pow(n+,mod-)%mod;
}
Iv Init(){
fac[]=;
R(i,,N)
fac[i]=(ll)(fac[i-])*i%mod;
invfac[N-]=Pow(fac[N-],mod-);
nR(i,N-,)
invfac[i-]=(ll)(invfac[i])*i%mod;
}
int f[N];
int main(){
//freopen("problem.in","r",stdin),freopen("problem.out","w",stdout);
Init();
int n=read();
switch(read()){
case :{
ll ans=;
for(re int i=;i<=n;i+=)
ans=(ll)((ans+C(n,i))*C(i,i>>)%mod*C((n-i),(n-i)>>)%mod)%mod;
//ans=(C(n,n>>1)%mod)*(C(n,n>>1)%mod)%mod;
print(ans);break;
}
case :{
printf("%d\n",Catalan(n>>));break;
}
case :{
n>>=,
f[]=,f[]=;
R(i,,n)
R(j,,i)
f[i]=((ll)(f[i]+f[i-j]*)*Catalan(j-)%mod)%mod;
print(f[n]);break;
}
default:{
int ans=;
for(re int i=;i<=n;i+=)
ans=(ans+(ll)(C(n,i))*Catalan(i>>)%mod*Catalan((n-i)>>)%mod)%mod;
print(ans);break;
}
}
return ;
}
problem_WA.cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <bitset> #define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define Mabs(a,b) ((a)>(b)?(a)-(b):(b)-(a))
#define Abs(a) (a)>0?(a):(-(a))
template <typename QvQ> inline QvQ Min2(QvQ a,QvQ b){if(a<b) return a;return b;}
template <typename QvQ> inline QvQ Max2(QvQ a,QvQ b){if(a>b) return a;return b;}
template <typename QvQ> inline QvQ Abs2(QvQ a){if(a>) return a;return -a;} #define inf 0x7f7f7f7f
#define dinf 0x3f3f3f3f
#define llinf 0x7f7f7f7f7f7f7f7f
#define lldinf 0x3f3f3f3f3f3f3f3f #define ll long long
#define rei register int
#define inv inline void
#define inb inline bool
#define ini inline int #define bl putchar(' ')
#define ed putchar('\n')
#define test std::cout<<"this:"
#define card system("pause") #define read2(a,b) read(a),read(b)
#define read3(a,b,c) read(a),read(b),read(c) #define MAXN 100005
#define MAXM 100005 char buf[<<],*p1=buf,*p2=buf,obuf[<<],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) template <typename QvQ>inv read(QvQ &x)
{
x=;int f=;
char c=getchar();
for(;c<''||c>'';c=getchar()) if(c=='-') f=-;
for(;c>=''&&c<='';c=getchar()) x=(x<<)+(x<<)+(c^);
x=x*f;
}
template <typename QvQ>inv write(QvQ x)
{
if(x<) x=-x,putchar('-');
if(x>) write(x/);
putchar(x%+'');
}
int n,q,cnt,len;
ll val,ans,a[MAXN],sum[MAXN/],lazy[MAXN/];
int piece[MAXN],left[MAXN/],right[MAXN/];
inv build()
{
memset(lazy,,sizeof(lazy));
read2(n,q);
len=sqrt(n);
cnt=n/len;
if(n%len) ++cnt;
for(rei i=;i<=n;++i) read(*(a+i)),*(piece+i)=(i-)/len+,sum[*(piece+i)]+=*(a+i);
for(rei i=;i<=cnt;++i) *(left+i)=(i-)*len+,*(right+i)=i*len; }
int main()
{
build();
int willing;
while(q--)
{
int l,r;
read3(willing,l,r);
if(willing==)
{
int val;read(val);
for(rei i=l;i<=Min(r,*(right+*(piece+l)));++i) a[i]+=val,sum[piece[i]]+=val;
for(rei i=r;i>=Max(l,*(left+*(piece+r)));--i) a[i]+=val,sum[piece[i]]+=val;
for(rei i=piece[l]+;i<=piece[r]-;++i) lazy[i]+=val;
}
else
{
ans=;
for(rei i=l;i<=Min(r,*(right+*(piece+l)));++i) ans+=a[i]+lazy[piece[i]];
for(rei i=r;i>=Max(l,*(left+*(piece+r)));--i) ans+=a[i]+lazy[piece[i]];
for(rei i=piece[l]+;i<=piece[r]-;++i) ans+=sum[i]+lazy[i]*(right[i]-left[i]+);
if(piece[l]==piece[r]) ans-=a[l]+lazy[piece[l]]+lazy[piece[r]]+a[r];
write(ans),ed;
}
}
return ;
}
problem_STD.cpp