信息学奥赛-入门级 题库
金币
【问题描述】
国王将金币作为工资,发放给忠诚的骑士。第一天,骑士收到一枚金币;之后两天(第二天和第三天),每天收到两枚金币;之后三天(第四、五、六天),每天收到三枚金币;之后四天(第七、八、九、十天),每天收到四枚金币……;这种工资发放模式会一直这样延续下去:当连续 N 天每天收到 N 枚金币后,骑士会在之后的连续 N+1 天里,每天收到 N+1 枚金币。
请计算在前 K 天里,骑士一共获得了多少金币。
【输入格式】
输入文件名为 coin.in。
输入文件只有 1 行,包含一个正整数 K,表示发放金币的天数。
【输出格式】
输出文件名为 coin.out。
输出文件只有 1 行,包含一个正整数,即骑士收到的金币数。
【输入输出样例 1】

【输入输出样例 1 说明】
骑士第一天收到一枚金币;第二天和第三天,每天收到两枚金币;第四、五、六天,每天收到三枚金币。因此一共收到 1+2+2+3+3+3=14 枚金币。
【输入输出样例 2】

【数据说明】
对于 100%的数据,1 ≤ K ≤ 10,000。
# include<stdio.h>
int main()
{
int m,n,k,s=0,count=1,flag=1;
scanf("%d",&k);
for(m=1;m<=k;count++,flag++){
for(n=1;n<=flag;n++){
s+=count;m++;
if(m>k) break;
}
}
printf("%d",s);
return 0;
}
珠心算测验
【问题描述】
珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练,既能够开发智力,又能够为日常生活带来很多便利,因而在很多学校得到普及。
某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合,集合中的数各不相同,然后要求学生回答:其中有多少个数,恰好等于集合中另外两个(不同的)数之和?
最近老师出了一些测验题,请你帮忙求出答案。
【输入】
输入文件名为 count.in。
输入共两行,第一行包含一个整数 n,表示测试题中给出的正整数个数。
第二行有 n 个正整数,每两个正整数之间用一个空格隔开,表示测试题中给出的正整数。
【输出】
输出文件名为 count.out。
输出共一行,包含一个整数,表示测验题答案。
【输入输出样例】

【样例说明】
由 1+2=3,1+3=4,故满足测试要求的答案为 2。注意,加数和被加数必须是集合中的两个不同的数。
【数据说明】
对于 100%的数据,3 ≤ n ≤ 100,测验题给出的正整数大小不超过 10,000。
#include <bits/stdc++.h>
#define MAXN 1e6+2
#define inf 0x3f3f3f3f
#define rep(x, a, b) for(int x=a; x<=b; x++)
#define per(x, a, b) for(int x=a; x>=b; x--)
using namespace std;
const int NC = 1e5+2;
//queue<int> que;
int num[200];
int cot;
int n;
bool visit[200];
int main()
{
cin>>n;
rep(i, 1, n)
{
cin>>num[i];
}
sort(num+1, num+1+n);
rep(i, 1, n)
{
rep(j, i+1, n)
{
if(num[i] != num[j])
{
rep(k, j+1, n)
{
if(num[i]+num[j] == num[k] && !visit[k])
{
cot++;
visit[k] = true;
}
}
}
}
}
cout<<cot;
return 0;
}
比例简化
【问题描述】
在社交媒体上,经常会看到针对某一个观点同意与否的民意调查以及结果。例如,对某一观点表示支持的有 1498 人,反对的有 902 人,那么赞同与反对的比例可以简单的记为1498:902。
不过,如果把调查结果就以这种方式呈现出来,大多数人肯定不会满意。因为这个比例的数值太大,难以一眼看出它们的关系。对于上面这个例子,如果把比例记为 5:3,虽然与真实结果有一定的误差,但依然能够较为准确地反映调查结果,同时也显得比较直观。
现给出支持人数 A,反对人数 B,以及一个上限 L,请你将 A 比 B 化简为 A’比 B’,要求在 A’和 B’均不大于 L 且 A’和 B’互质(两个整数的最大公约数是 1)的前ᨀ下,A’/B’ ≥ A/B且 A’/B’ - A/B 的值尽可能小。
【输入】
输入文件名为 ratio.in。
输入共一行,包含三个整数 A,B,L,每两个整数之间用一个空格隔开,分别表示支持人数、反对人数以及上限。
【输出】
输出文件名为 ratio.out。
输出共一行,包含两个整数 A’,B’,中间用一个空格隔开,表示化简后的比例。
【输入输出样例】

【数据说明】
对于 100%的数据,1 ≤ A ≤ 1,000,000,1 ≤ B ≤ 1,000,000,1 ≤ L ≤ 100,A/B ≤ L。
#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <cstring>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
using namespace std;
typedef long long ll;
typedef pair<int,int> pa;
const int N=100005;
const int mod=99999997;
int x,y,l;
int a,b;
int gcd(int x,int y)
{
if(x<y) return gcd(y,x);
if(y==0) return x;
return gcd(y,x%y);
}
int main()
{
scanf("%d%d%d",&x,&y,&l);
double t1,t2,t3;
t1=x*1.0/y;
t3=l*1.0;
for(int i=1;i<=l;i++)
{
for(int k=1;k<=l;k++)
{
t2=i*1.0/k;
if(t2>=t1 &&gcd(i,k)==1 && t2-t1<t3)
{
a=i;
b=k;
t3=t2-t1;
}
}
}
printf("%d %d\n",a,b);
return 0;
}
小朋友的数字
【问题描述】
有 n 个小朋友排成一列。每个小朋友手上都有一个数字,这个数字可正可负。规定每个小朋友的特征值等于排在他前面(包括他本人)的小朋友中连续若干个(最少有一个)小朋友手上的数字之和的最大值。
作为这些小朋友的老师,你需要给每个小朋友一个分数,分数是这样规定的:第一个小朋友的分数是他的特征值,其它小朋友的分数为排在他前面的所有小朋友中(不包括他本人),小朋友分数加上其特征值的最大值。
请计算所有小朋友分数的最大值,输出时保持最大值的符号,将其绝对值对 p 取模后
输出。
【输入】
输入文件为 number.in。
第一行包含两个正整数 n、p,之间用一个空格隔开。
第二行包含 n 个数,每两个整数之间用一个空格隔开,表示每个小朋友手上的数字。
【输出】
输出文件名为 number.out。
输出只有一行,包含一个整数,表示最大分数对 p 取模的结果。
【输入输出样例 1】

【输入输出样例说明】
小朋友的特征值分别为 1、3、6、10、15,分数分别为 1、2、5、11、21,最大值 21对 997 的模是 21。
【输入输出样例 2】

【输入输出样例说明】
小朋友的特征值分别为-1、-1、-1、-1、-1,分数分别为-1、-2、-2、-2、-2,最大值
-1 对 7 的模为-1,输出-1。
【数据范围】
对于 50%的数据,1 ≤ n ≤ 1,000,1 ≤ p ≤ 1,000所有数字的绝对值不超过 1000;
对于 100%的数据,
其他数字的绝对值均不超过![]()
#include<bits/stdc++.h>
using namespace std;
#define int __int128
int read(){
int x=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){
if(c=='-'){
f=-1;
}
c=getchar();
}
while(c<='9'&&c>='0'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
int n,p,f[1000006],ca,te[1000006],score[1000006],ans;
signed main(){
// freopen("number.in","r",stdin);
// freopen("number.out","w",stdout);
n=read();
p=read();
ca=read();
te[1]=f[1]=ca;
for(int i=2;i<=n;i++){
ca=read();
f[i]=max(ca,f[i-1]+ca);
}
int maxx=f[1];
for(int i=2;i<=n;i++){
te[i]=max(f[i],maxx);
if(f[i]>maxx){
maxx=f[i];
}
}
score[1]=te[1];
int temp=score[1]+te[1];
ans=score[1];
for(int i=2;i<=n;i++){
score[i]=temp;
temp=max(temp,score[i]+te[i]);
ans=max(ans,score[i]);
}
write(ans%p);
return 0;
}
质因数分解
【问题描述】
已知正整数 n 是两个不同的质数的乘积,试求出较大的那个质数。
【输入】
输入文件名为 prime.in。
输入只有一行,包含一个正整数 n。
【输出】
输出文件名为 prime.out。
输出只有一行,包含一个正整数 p,即较大的那个质数。
【输入输出样例】

【数据范围】
对于 60%的数据,6 ≤ n ≤ 1000。
对于 100%的数据,
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
int i,j;
for(i=2;i<=sqrt(t);i++)
{
if(t%i==0)
{
cout<<t/i<<endl;
break;
}
}
return 0;
}
寻宝
【问题描述】 传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏 宝楼,藏宝楼的门口竖着一个木板,上面写有几个大字:寻宝说明书。说明书的内容如下:
藏宝楼共有 N+1 层,最上面一层是顶层,顶层有一个房间里面藏着宝藏。除了顶层外,藏宝楼另有 N 层,每层 M 个房间,这 M 个房间围成一圈并按逆时针方向依次编号为 0,…,M-1。其中一些房间有通往上一层的楼梯,每层楼的楼梯设计可能不同。每个房间里有一个指示牌,指示牌上有一个数字 x,表示从这个房间开始按逆时针方向选择第 x 个有楼梯的房间(假定该房间的编号为 k),从该房间上楼,上楼后到达上一层的 k 号房间。比如当前房间的指示牌上写着 2,则按逆时针方向开始尝试,找到第 2 个有楼梯的房间,从该房间上楼。如果当前房间本身就有楼梯通向上层,该房间作为第一个有楼梯的房间。
寻宝说明书的最后用红色大号字体写着:“寻宝须知:帮助你找到每层上楼房间的指示牌上的数字(即每层第一个进入的房间内指示牌上的数字)总和为打开宝箱的密钥”。
请帮助小明算出这个打开宝箱的密钥。
【输入】
输入文件为 treasure.in。
第一行 2 个整数 N 和 M,之间用一个空格隔开。N 表示除了顶层外藏宝楼共 N 层楼,M 表示除顶层外每层楼有 M 个房间。
接下来 N*M 行,每行两个整数,之间用一个空格隔开,每行描述一个房间内的情况,其中第(i-1)*M+j 行表示第 i 层 j-1 号房间的情况(i=1, 2, …, N;j=1, 2, … ,M)。第一个整数表示该房间是否有楼梯通往上一层(0 表示没有,1 表示有),第二个整数表示指示牌上的数字。注意,从 j 号房间的楼梯爬到上一层到达的房间一定也是 j 号房间。
最后一行,一个整数,表示小明从藏宝楼底层的几号房间进入开始寻宝(注:房间编号从 0 开始)。
【输出】
输出文件名为 treasure.out。
输出只有一行,一个整数,表示打开宝箱的密钥,这个数可能会很大,请输出对 20123取模的结果即可。
【输入输出样例】

【输入输出样例说明】
第一层:
0 号房间,有楼梯通往上层,指示牌上的数字是 2;
1 号房间,无楼梯通往上层,指示牌上的数字是 3;
2 号房间,有楼梯通往上层,指示牌上的数字是 4;
第二层:
0 号房间,无楼梯通往上层,指示牌上的数字是 1;
1 号房间,有楼梯通往上层,指示牌上的数字是 5;
2 号房间,有楼梯通往上层,指示牌上的数字是 2;
小明首先进入第一层(底层)的 1 号房间,记下指示牌上的数字为 3,然后从这个房间开始,沿逆时针方向选择第3 个有楼梯的房间 2 号房间进入,上楼后到达第二层的2 号房间,记下指示牌上的数字为 2,由于当前房间本身有楼梯通向上层,该房间作为第一个有楼梯的房间。因此,此时沿逆时针方向选择第 2 个有楼梯的房间即为 1 号房间,进入后上楼梯到达顶层。这时把上述记下的指示牌上的数字加起来,即 3+2=5,所以打开宝箱的密钥就是 5。
【数据范围】
对于 50%数据,有 0<N≤1000,0<x≤10000;
对于 100%数据,有 0<N≤10000,0<M≤100,0<x≤1,000,000。
#include<iostream>
#include<cstdio>
using namespace std;
const int N(10008),M(108),MODN=20123;
int a[N][M],f[N][M],sum[N]={0};
int main()
{
//freopen("treasure.in","r",stdin);
//freopen("treasure.out","w",stdout);
int n,m,i,j,k;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
for (j=0;j<m;j++)
{
scanf("%d%d",&f[i][j],&a[i][j]);
if (f[i][j]) sum[i]++;
}
int ans=0;
scanf("%d",&j);
for (i=1;i<=n;i++)
{
ans=(ans+a[i][j])%MODN;
a[i][j]%=sum[i];
if (a[i][j]==0) a[i][j]=sum[i];
for (k=a[i][j];k>0;)
{
if (f[i][j])
k--;
if (k>0) j=(j+1)%m;
}
}
printf("%d\n",ans);
return 0;
}
摆花
【问题描述】
小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共 m 盆。通过调查顾客的喜好,小明列出了顾客最喜欢的 n 种花,从 1 到 n 标号。为了在门口展出更多种花,规定第 i 种花不能超过 ai盆,摆花时同一种花放在一起,且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算,一共有多少种不同的摆花方案。
【输入】
输入文件 flower.in,共 2 行。
第一行包含两个正整数 n 和 m,中间用一个空格隔开。
第二行有 n 个整数,每两个整数之间用一个空格隔开,依次表示 a1、a2、……an。
【输出】
输出文件名为 flower.out。
输出只有一行,一个整数,表示有多少种方案。注意:因为方案数可能很多,请输出方案数对 1000007 取模的结果。
【输入输出样例 1】

【输入输出样例说明】
有 2 种摆花的方案,分别是(1,1,1,2), (1,1,2,2)。括号里的 1 和 2 表示两种花, 比如第一个方案是前三个位置摆第一种花,第四个位置摆第二种花。
【数据范围】
对于 20%数据,有 0<n≤8,0<m≤8,0≤ai≤8;
对于 50%数据,有 0<n≤20,0<m≤20,0≤ai≤20;
对于 100%数据,有 0<n≤100,0<m≤100,0≤ ai≤100。
#include <algorithm>
#include<iostream>
using namespace std;
int A[105][105];
int a[105];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
A[0][0]=1; //不摆放花也是一种方案
for(int i=1;i<=n;i++)//花的种类
{
for(int j=0;j<=m;j++)//花的朵数
{
for(int k=0;k<=min(a[i],j);k++)//k从0开始表示不一定所有种类的花都要摆上,选择min(a[i],j)是因为第i种花一共只有a[i]盆,要够放
{
A[i][j]=(A[i][j]+A[i-1][j-k])%1000007;
}
}
}
cout<<A[n][m]%1000007<<endl;
return 0;
}
校门外的树
【问题描述】
某校大门外长度为L的马路上有一排树,每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置;数轴上的每个整数点,即0,1,2,……,L,都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些区域中的树(包括区域端点处的两棵树)移走。你的任务是计算将这些树都移走后,马路上还有多少棵树。
【输入文件】
输入文件tree.in的第一行有两个整数:L(1 <= L <= 10000)和 M(1 <= M <= 100),L代表马路的长度,M代表区域的数目,L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数,用一个空格隔开,表示一个区域的起始点和终止点的坐标。
【输出文件】
输出文件tree.out包括一行,这一行只包含一个整数,表示马路上剩余的树的数目。
【样例输入】
500 3
150 300
100 200
470 471
【样例输出】
298
【数据规模】
对于20%的数据,区域之间没有重合的部分;
对于其它的数据,区域之间有重合的情况。
采药
【问题描述】
辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”
如果你是辰辰,你能完成这个任务吗?
【输入文件】
输入文件medic.in的第一行有两个整数T(1 <= T <= 1000)和M(1 <= M <= 100),用一个空格隔开,T代表总共能够用来采药的时间,M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某株草药的时间和这株草药的价值。
【输出文件】
输出文件medic.out包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。
【样例输入】
70 3
71 100
69 1
1 2
【样例输出】
3
【数据规模】
对于30%的数据,M <= 10;
对于全部的数据,M <= 100。
循环
【问题描述】
乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天,他突然对数的正整数次幂产生了兴趣。
众所周知,2的正整数次幂最后一位数总是不断的在重复2,4,8,6,2,4,8,6……我们说2的正整数次幂最后一位的循环长度是4(实际上4的倍数都可以说是循环长度,但我们只考虑最小的循环长度)。类似的,其余的数字的正整数次幂最后一位数也有类似的循环现象:

这时乐乐的问题就出来了:是不是只有最后一位才有这样的循环呢?对于一个整数n的正整数次幂来说,它的后k位是否会发生循环?如果循环的话,循环长度是多少呢?
注意:
1. 如果n的某个正整数次幂的位数不足k,那么不足的高位看做是0。
2. 如果循环长度是L,那么说明对于任意的正整数a,n的a次幂和a + L次幂的最后k位都相同。
【输入文件】
输入文件circle.in只有一行,包含两个整数n(1 <= n < 10100)和k(1 <= k <= 100),n和k之间用一个空格隔开,表示要求n的正整数次幂的最后k位的循环长度。
【输出文件】
输出文件circle.out包括一行,这一行只包含一个整数,表示循环长度。如果循环不存在,输出-1。
【样例输入】
32 2
【样例输出】
4
【数据规模】
对于30%的数据,k <= 4;
对于全部的数据,k <= 100。
火星人
【问题描述】
人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言,但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的,首先,火星人把一个非常大的数字告诉人类科学家,科学家破解这个数字的含义后,再把一个很小的数字加到这个大数上面,把结果告诉火星人,作为人类的回答。
火星人用一种非常简单的方式来表示数字——掰手指。火星人只有一只手,但这只手上有成千上万的手指,这些手指排成一列,分别编号为1,2,3……。火星人的任意两根手指都能随意交换位置,他们就是通过这方法计数的。
一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指——拇指、食指、中指、无名指和小指分别编号为1,2,3,4和5,当它们按正常顺序排列时,形成了5位数12345,当你交换无名指和小指的位置时,会形成5位数12354,当你把五个手指的顺序完全颠倒时,会形成54321,在所有能够形成的120个5位数中,12345最小,它表示1;12354第二小,它表示2;54321最大,它表示120。下表展示了只有3根手指时能够形成的6个3位数和它们代表的数字:
三进制数
123
132
213
231
312
321
代表的数字
1
2
3
4
5
6
现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指,科学家会告诉你要加上去的很小的数。你的任务是,把火星人用手指表示的数与科学家告诉你的数相加,并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。
【输入文件】
输入文件martian.in包括三行,第一行有一个正整数N,表示火星人手指的数目(1 <= N <= 10000)。第二行是一个正整数M,表示要加上去的小整数(1 <= M <= 100)。下一行是1到N这N个整数的一个排列,用空格隔开,表示火星人手指的排列顺序。
【输出文件】
输出文件martian.out只有一行,这一行含有N个整数,表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开,不能有多余的空格。
【样例输入】
5
3
1 2 3 4 5
【样例输出】
1 2 4 5 3
【数据规模】
对于30%的数据,N<=15;
对于60%的数据,N<=50;
对于全部的数据,N<=10000;
数字游戏(Game.pas)
【问题描述】丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前有一圈整数(一共n个),你要按顺序将其分为m个部分,各部分内的数字相加,相加所得的m个结果对10取模后再相乘,最终得到一个数k。游戏的要求是使你所得的k最大或者最小。
例如,对于下面这圈数字(n=4,m=2):

当要求最小值时,((2-1) mod 10)×((4+3) mod 10)=1×7=7,要求最大值时,为((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是,无论是负数还是正数,对10取模的结果均为非负值。
丁丁请你编写程序帮他赢得这个游戏。
【输入格式】输入文件第一行有两个整数,n(1≤n≤50)和m(1≤m≤9)。以下n行每行有个整数,其绝对值不大于104,按顺序给出圈中的数字,首尾相接。
【输出格式】输出文件有两行,各包含一个非负整数。第一行是你程序得到的最小值,第二行是最大值。
【输入样例】
4 2
4
3
-1
2
【输出样例】
7
81
麦森数(Mason.pas)
【问题描述】形如
的素数称为麦森数,这时P一定也是个素数。但反过来不一定,即如果P是个素数,
不一定也是素数。到1998年底,人们已找到了37个麦森数。最大的一个是P=3021377,它有909526位。麦森数有许多重要应用,它与完全数密切相关。
任务:从文件中输入P(1000<P<3100000),计算
的位数和最后500位数字(用十进制高精度数表示)
【输入格式】
文件中只包含一个整数P(1000<P<3100000)
【输出格式】
第一行:十进制高精度数
的位数。
第2-11行:十进制高精度数
的最后500位数字。(每行输出50位,共输出10行,不足500位时高位补0)
不必验证
与P是否为素数。
【输入样例】
1279
【输出样例】
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087
选数
[问题描述]:
已知 n 个整数 x1,x2,…,xn,以及一个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。例如当 n=4,k=3,4 个整数分别为 3,7,12,19 时,可得全部的组合与它们的和为:
3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34。
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数:3+7+19=29)。
[输入]:
键盘输入,格式为:
n , k (1<=n<=20,k<n)
x1,x2,…,xn (1<=xi<=5000000)
[输出]:
屏幕输出,格式为:
一个整数(满足条件的种数)。
[输入输出样例]:
输入:
4 3
3 7 12 19
输出:
1
数的计算
问题描述
我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:
1. 不作任何处理;
2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
3. 加上数后,继续按此规则进行处理,直到不能再加自然数为止.
样例: 输入: 6
满足条件的数为 6 (此部分不必输出)
16
26
126
36
136
输出: 6
最大公约数和最小公倍数问题
问题描述
输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数
条件:
1.P,A是正整数
2.要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.
样例
输入:x0=3 yo=60
输出:4
说明(不用输出)此时的 P Q 分别为:
3 60
15 12
12 15
60 3
所以:满足条件的所有可能的两个正整数的个数共4种.
微信步数(walk)
【题目描述】
小 C 喜欢跑步,并且非常喜欢在微信步数排行榜上刷榜,为此他制定了一个刷微信步数的计划。
他来到了一处空旷的场地,处于该场地中的人可以用 k 维整数坐标 (a1, a2, · · · , ak)来表示其位置。场地有大小限制,第 i 维的大小为 wi,因此处于场地中的人其坐标应满足 1 ≤ ai ≤ wi(1 ≤ i ≤ k)。
小 C 打算在接下来的 P = w1 × w2 × · · · × wk 天中,每天从场地中一个新的位置出发,开始他的刷步数计划(话句话说,他将会从场地中每个位置都出发一次进行计划)。
他的计划非常简单,每天按照事先规定好的路线行进,每天的路线由 n 步移动构成,每一步可以用 ci 与 di 表示:若他当前位于 (a1, a2, · · · , aci, · · · , ak),则这一步他将会走到 (a1, a2, · · · , aci + di, · · · , ak),其中 1 ≤ ci ≤ k,di ∈ {−1, 1}。小 C 将会不断重复这个路线,直到他走出了场地的范围才结束一天的计划。(即走完第 n 步后,若小 C 还在场内,他将回到第 1 步从头再走一遍)。
小 C 对自己的速度非常有自信,所以他并不在意具体耗费的时间,他只想知道 P天之后,他一共刷出了多少步微信步数。请你帮他算一算。
【输入格式】
从文件 walk.in 中读入数据。
第一行两个用单个空格分隔的整数 n,k。分别表示路线步数与场地维数。
接下来一行 k 个用单个空格分隔的整数 wi,表示场地大小。
接下来 n 行每行两个用单个空格分隔的整数 ci,di,依次表示每一步的方向,具体意义见题目描述。
【输出格式】
输出到文件 walk.out 中。
仅一行一个整数表示答案。答案可能很大,你只需要输出其对 109 + 7 取模后的值。
若小 C 的计划会使得他在某一天在场地中永远走不出来,则输出一行一个整数 -1。
【样例 1 输入】
3 2
3 3
1 1
2 -1
1 1
【样例 1 输出】
21
【样例 1 解释】
从 (1, 1) 出发将走 2 步,从 (1, 2) 出发将走 4 步,从 (1, 3) 出发将走 4 步。
从 (2, 1) 出发将走 2 步,从 (2, 2) 出发将走 3 步,从 (2, 3) 出发将走 3 步。
从 (3, 1) 出发将走 1 步,从 (3, 2) 出发将走 1 步,从 (3, 3) 出发将走 1 步。
共计 21 步。
【样例 2 输入】
5 4
6 8 6 5
3 1
2 1
1 1
2 1
2 -1
【样例 2 输出】
10265
【数据范围】

对于所有测试点,保证 1 ≤ n ≤ 5 × 105,1 ≤ k ≤ 10,1 ≤ wi ≤ 109,di ∈ {−1, 1}。