3349:练60.3 余数个数
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 221 通过数: 176
题目链接:信息学奥赛一本通-编程启蒙(C++版)在线评测系统
【题目描述】
给出 10 个整数,问这些整数 (mod42)后有多少个不同的余数。
【输入】
输入共 10行,每行一个不超过 10^9 的正整数。
【输出】
一个整数,表示不同的余数个数。
【输入样例】
39
40
41
42
43
44
82
83
84
85
【输出样例】
6
【提示】
【样例说明】
39 mod 42 = 39
40 mod 42 = 40
41 mod 42 = 41
42 mod 42 = 0
43 mod 42 = 1
44 mod 42 = 2
82 mod 42 = 40
83 mod 42 = 41
84 mod 42 = 0
85 mod 42 = 1
结果为 6 个不同的余数。
思路:
我们思考一下,我们最多能找到多少个不同的余数?
我们最多能找到42个,分别是:0、1、2、3、4、……、40、41(因为取模42)
我们再想一下,有多少个不同的余数,是不是就是统计42个数中,有多少个已经出现过?
那我们怎么知道有几个不同的余数(有多少个已经出现过)呢?
因为我们最多只有42个余数,所以我们可以定义一个bool型的数组bj[50]来记录,bj[i]表示是否出现过i这个余数(1表示出现过,0表示没有出现过)(比如b[1]=1表示出现过1这个余数)这样我们就可以表示出某个余数是否出现过
那么,我们只要统计出现过的余数有多少个出现过,那我们就可以知道有几个不同的余数了
代码:
#include<bits/stdc++.h>
using namespace std;
bool bj[50];
int main(){
long long a[11];
for(int i=1;i<=10;i++){
cin>>a[i];
int ls=a[i]%42;
bj[ls]=1;
}
long long cnt=0;
for(int i=0;i<=42;i++){
if(bj[i]==1){
cnt++;
}
}
cout<<cnt;
return 0;
}