【问题讲述】
概念”组合数”S(n,m)代表将 n 个不同之素拆分成 m 个非空集合的方案
数.举独栗子,将{1,2,3}拆分成 2
个集有({1},{2,3}),({2},{1,3}),({3},{1,2})三种植拆分
方法.
小猫想掌握,如果让定 n,m 以及 k,对于有着的
0<=i<=n,0<=j<=min(i,m),有微微对
(i,j),满足 S(i,j)是 k 的倍数.
注意,0 也是 k 的倍数,S(0,0)=1,对于 i>=1,S(i,0)=0.
【输入格式】
从 problem.in 种读入数据
率先行有三三两两独整数 t,k,t 代表该测试点总共有微组测试数据.
连通下去 t 行,每行两只整数 n,m.
【输出格式】
输出到文件 problem.out 中
t 行,每行一个平头代表有的
0<=i<=n,0<=j<=min(i,m),有微对(i,j),满足 S(i,j)
是 k 的倍数.
【样例输入 1】
12
33
【样例输出 1】
3
【样例说明 1】
S(1,0),S(2,0),S(3,0)均是 2 的倍数
【样例输入 2】
25
45
67
【样例输出 2】
4
12
【数据规模和约定】
对于 20%的数据,满足 n,m<=7,k<=5
对于 60%的数据,满足 n,m<=100,k<=10
对每个子任务,都发 50%的多寡满足 t=1
对于 100%的数据,满足
1<=n<=2000,1<=m<=2000,2<=k<=21,1<=t<=10000

  

斯特林数(II)

公约数和倍

时间范围:1000 ms  |  内存限制:65535 KB

难度:1

 

描述
小明于一个问题让难休了,现在亟需你帮助拉。问题是:给来片只刚整数,求来其的最大公约数和最小公倍数。

 

输入
首先履输入一个整数n(0<n<=10000),表示出n组测试数据;
就的n行输入两个整数i,j(0<i,j<=32767)。

输出
输出每组测试数据的最大公约数和最小公倍数

样例输入
3
6 6
12 11
33 22

样例输出
6 6
1 132
11 66

图片 1

 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char *argv[])
{
int n,k;
int i,j;
int t,m;
int temp=0;
int count1=0;
int count2=0;
int arr1[100]={0};
int arr2[100];
scanf(“%d”,&n);
for(k=0;k<n;k++)
{
scanf(“%d”,&i);
scanf(“%d”,&j);
if(i<j)
{
temp=i;
i=j;
j=temp;
}
for(t=1;t<j+1;t++)
{
if(i%t==0&&j%t==0) //最大公约数
{
arr1[count1]=t;
count1++;
}
}
for(m=i;m<i*j+1;m++) //最小公倍数
{
if(m%i==0&&m%j==0)
{
arr2[count2]=m;
count2++;
}
}
printf(“%d “,arr1[count1-1]);
printf(“%d “,arr2[0]);
count1=count2=0; //一定要记清零
printf(“\n”); //转换
}
return 0;
}

S[i][j]=S[i-1][j-1]+j*S[i-1][j]

解释一下:

于i,j,它可以独自构成j集合,前面要起j-1单集

为堪放入前面的汇聚

因为集合非空,所以前面的集结要出j个,有j栽选择

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int k,t,n,m;
 7 long long S[2001][2001],a[2001][2001];
 8 int main()
 9 {int i,j;
10   cin>>t>>k;
11   S[0][0]=1;
12   for (i=1;i<=2000;i++)
13     {
14       S[i][0]=0;
15       for (j=1;j<=i;j++)
16     {
17       S[i][j]=(S[i-1][j-1]+S[i-1][j]*j)%k;
18     }
19     }
20   for (i=0;i<=2000;i++)
21     {
22       for (j=0;j<=i;j++)
23     {
24       if (S[i][j]==0)
25         a[i][j]=1;
26     }
27     }
28   for (i=1;i<=2000;i++)
29     {
30       for (j=1;j<=2000;j++)
31     a[i][j]+=a[i][j-1];
32     }
33   for (i=1;i<=2000;i++)
34     {
35       for (j=0;j<=2000;j++)
36     a[i][j]+=a[i-1][j];
37     }
38   while (t--)
39     {
40       scanf("%d%d",&n,&m);
41       printf("%lld\n",a[n][m]);
42     }
43 }

 

相关文章

网站地图xml地图