组合数
http://oj.icode8.cn/problem.php?id=1881
题目描述
有两堆连续的数字,第一堆包含[1,n]n个数字,第二堆包含[1,m]m个数字,现想要从两堆中各挑选出一个整数x,y,使得x,y的和为7的倍数,请问有多少种组合的方式。
输入
n和m(1<=m,n<=1000000)
输出
多少种组合。
样例输入 Copy
6 7
样例输出 Copy
6
提示
(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)
个人理解:
由于数据过多,可以只对余数经行计算,7以下的余数只有0,1,2,3,4,5,6.所以再多情况都可以分为这其中情况,当然举一反三,其他情况也是如此。
题解分析:
根据样例输入,n=6,m=7;从1~n都对7取余数,&7,从1~m都对7取余数%7,得到的余数排好。看提示可知,(1,6)在一组,那就让他们的余数相乘*【为什么不想加我也不知道,只知道相加不对,数字太大了,所以*了】。
根据提示可知,一组数据相加都是7,则可以分为a【i】,b【7-i】,那么这时候a【0】与b【0】就是特殊情况了,就要分开计算了。sum一定要是long long类型的,否则会报错。
大概情况就是这样,简单题。
代码如下:
#include<bits/stdc++.h>
using namespace std;
long long a[7],b[7];
long long sum=0;
int main (){
long long n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
a[i%7]++;
for(int i=1;i<=m;i++)
b[i%7]++;
for(int i=1;i<=6;i++){
if(a[i] && b[7-i]){
sum+=a[i]*b[7-i];
}
}
if(a[0] && b[0])
sum+=a[0]*b[0];
cout<<sum;
}
- 复制链接
- 举报