• 首页
  • 教育理念
  • 文章专题
  • 编程教程
    • – Scratch编程教程
    • – AppInventor编程
    • – Python编程教程
    • – NOIP信息学奥赛
    • – C/C++编程教程
    • – JS编程教程
  • 少儿编程学院
    • – 在线课程
    • – 学院名师
    • – 动态资讯
  • 少儿编程社区
    • – 在线编程
    • – 编程作品
    • – 专题创作
  • 更多
    • – APP客户端
    • – 关于我们
    • – 寻求合作
    • – 少儿编程联盟
投稿 登录 注册
  • 首页
  • 文章专题
  • 教育理念
  • 编程教程
  • 少儿编程学院
  • 微信公众号
  • APP客户端
少儿编程学院
少儿编程教育-微信公众号
首页 › 编程教程 › NOIP信息学奥赛 › 正文
NOIP信息学奥赛信息竞赛编程竞赛

NOIP复赛复习(三)文件读写与数论模板

主编主编 NOIP信息学奥赛 2017-10-02 2,656 0

文件读入读出

假设题目名为“add”,那么文件夹名为“add”,c++程序名为“add.cpp”,读入文件名为“add.in”,输出文件名为“add.out”。四个的拼写均不可有误,包括大小写差异。千万不要调试后就忘记修改文件读入读出了。
#include<cstdio>
int main(){
freopen("add.in","r",stdin);//read
freopen("add.out","w",stdout);//write
}


数论算法

1、线性筛

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn=200005;
int prime[maxn];
bool not_prime[maxn];
int main()
{
int n,cnt=0;
scanf("%d",&n);
memset(not_prime,0,sizeof(not_prime));
not_prime[1]=true;
for(inti=2;i<=n;i++)
{
if(!not_prime[i])
prime[++cnt]=i;
for(intj=1;j<=cnt;j++)
{
if(prime[j]*i>n)    break;
not_prime[prime[j]*i]=true;
if(i%prime[j]==0) break;
}
}
for(inti=1;i<=cnt;i++)
printf("%d ",prime[i]);
return 0;
}

2、埃氏筛

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
inline int read()
{
char c;
c=getchar();
for(;c>'9'||c<'0';c=getchar());
int sum=0;
for(;c<='9'&&c>='0';c=getchar())sum=sum*10+c-48;
return sum;
}
int n,m;
bool f[10010000];
int main()
{
n=read(),m=read();
memset(f,true,sizeof(f));
f[0]=f[1]=false;
for(inti=2;i<=n;i++)
if(f[i])
for(intj=2;i*j<=n;f[i*j]=false,j++);
for(inti=1;i<=m;i++)
{
int x;
x=read();
if(f[x])printf("Yes\n");
elseprintf("No\n");
}
return 0;
}

3、拓展欧几里得算法

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int x,y;
int exgcd(int a,int b)
{
if(!b)
{
x=1;
y=0;
return a;
}
else
{
int t;
intd=exgcd(b,a%b);
t=x;
x=y;
y=t-a/b*x;
return d;
}
}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
exgcd(a,b);
// cout<<__gcd(a,b)<<endl;
cout<<x<<" "<<y<<endl;
return 0;
}

4、GCD&LCM

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int gcd(int a,int b)
{
if(!b) returna;
else returngcd(b,a%b);
}
int lcm(int a,int b)
{
returna/gcd(a,b)*b;
}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
cout<<gcd(a,b)<<" "<<lcm(a,b)<<endl;
return 0;
}

5、分解质因数

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int main()
{
long long n;
scanf("%lld",&n);
for(long longi=2;i<=n;i++)
{
while(n!=i)
{
if(n%i==0)
{
printf("%lld*",i);
n=n/i;
}
elsebreak;
}
}
printf("%lld",n);
return 0;
}

6、大数翻倍法

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int a[233],mo[233];
int gcd(int a,int b)
{
if(!b) returna;
else returngcd(b,a%b);
}
int lcm(int a,int b)
{
returna/gcd(a,b)*b;
}
int main()
{
int n;
scanf("%d",&n);
for(inti=1;i<=n;i++)
scanf("%d%d",&a[i],&mo[i]);
intans=0,nowmo=1;
for(inti=1;i<=n;i++)
{
intother=a[i],othermo=mo[i];
if(othermo>nowmo)
{
swap(ans,other);
swap(nowmo,othermo);
}
while(ans%othermo!=other)
ans+=nowmo;
nowmo=lcm(nowmo,othermo);
}
printf("%d",ans);
}

7、快速幂

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1007;
int xx(int a,int n,int MOD)
{
int ret=1;
int tmp=a%MOD;
while(n)
{
if(n&1)
ret=ret*tmp%MOD;
tmp=tmp*tmp%MOD;
n>>=1;
}
return ret;
}
int main()
{
int m,n;
while(scanf("%d%d",&m,&n)==2)
{
printf("%d\n",xx(m,n,MOD));
}
}

8、位运算

NOIP复赛复习(三)文件读写与数论模板-少儿编程教育网 NOIP复赛复习(三)文件读写与数论模板-少儿编程教育网
喜欢 (0)
打赏
  • 打赏支付宝扫一扫
  • 打赏微信扫一扫
微博 微信 QQ

微信扫一扫,分享到朋友圈

微信公众号
编程少年Scratch实物积木
少儿编程教育-微信公众号
上一篇

NOIP复赛复习(二)竞赛环境与注意事项

下一篇

NOIP复赛复习(四)读写外挂与高精度模板

猜你喜欢

  • 第二届全国中学生网络安全竞赛即将在西安电子科大举办!

    第二届全国中学生网络安全竞赛即将在西安电子科大举办!

  • 严查违规竞赛,29项全国中小学生竞赛活动名单公布!

    严查违规竞赛,29项全国中小学生竞赛活动名单公布!

  • 教育部:2019年度中小学生全国性竞赛活动名单公示

    教育部:2019年度中小学生全国性竞赛活动名单公示

  • 第二十届全国中小学电脑制作活动通知

    第二十届全国中小学电脑制作活动通知

  • 2018年全国青少年创意编程大赛,终评活动即将开启!

    2018年全国青少年创意编程大赛,终评活动即将开启!

  • STEAM教育专题 | 源自硅谷的机器人教育机构萝卜太辣

    STEAM教育专题 | 源自硅谷的机器人教育机构萝卜太辣

主编
主编官方

我真的不是自黑!

中国STEAM教育2018年度风云榜

微信公众号

推荐专题

  • 有趣的少儿编程游戏推荐

    查看专题
  • 国外优秀的少儿编程教育

    查看专题
  • S科学-T技术-E工程-M数学

    查看专题

猜你喜欢

  • NOIP复赛复习(十五)动态规划巩固与提高
    2017-10-16

    NOIP复赛复习(十五)动态规划巩固与提高

  • 教育部推教育信息化2.0行动计划:人工智能融入个性化教学

    教育部推教育信息化2.0行动计划:人工智能融入个性化教学

    2018-05-23
  • STEAM教育体系,世界公认的STEAM教育人才培养方案!

    STEAM教育体系,世界公认的STEAM教育人才培养方案!

    2018-04-10
  • 广东粤教版教材Scratch少儿编程-第16课-飞机大战(上)

    广东粤教版教材Scratch少儿编程-第16课-飞机大战(上)

    2018-01-26
  • Scratch2.0少儿编程教程集合

    Scratch2.0少儿编程教程集合

    2017-06-29

热门文章

  • 新型冠状病毒肺炎,儿童真的不易感?专家组组长:论据尚不充分!
    2020-01-24 57,448

    新型冠状病毒肺炎,儿童真的不易感?专家组组长:论据尚不充分!

  • 9个青少儿防疫问题,北京大学国际医院儿科专家权威解答!
    2020-02-08 45,150

    9个青少儿防疫问题,北京大学国际医院儿科专家权威解答!

热门标签

鲨鱼公园高考改革高考加分青橙创客青少儿防疫阿部和广错误观念逻辑思维费米科学贝尔科教谷歌教育计算机科学计算机思维解决方案西瓜创客

微信公众号

热门文章 热门标签 年度归档 少儿编程教育联盟

Copyright © 2021 少儿编程教育网 粤ICP备17057575号 · Designed by shaoerbc.org

大家都在搜

  • Scratch教程
  • scratch2下载
  • Scratch编程
  • 编程思维
  • 信息学奥赛
  • STEM教育
  • 编程一小时
  • 自主招生
  • 少儿编程竞赛

关注我们的公众号

微信公众号