2014
03-01

# Least common multiple

Partychen like to do mathematical problems. One day, when he was doing on a least common multiple(LCM) problem, he suddenly thought of a very interesting question: if given a number of S, and we divided S into some numbers , then what is the largest LCM of these numbers? partychen thought this problems for a long time but with no result, so he turned to you for help!
Since the answer can very big,you should give the answer modulo M.

There are many groups of test case.On each test case only two integers S( 0 < S <= 3000) and M( 2<=M<=10000) as mentioned above.

There are many groups of test case.On each test case only two integers S( 0 < S <= 3000) and M( 2<=M<=10000) as mentioned above.

6 23

6

Hint: you can divied 6 as 1+2+3 and the LCM(1,2,3)=6 is the largest so we output 6%23=6.

#include<cstdio>
#include<vector>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define M 10005
using namespace std;
double dp[M];
int p[M];
int prime[M],cnt,n;
bool f[M];
void init()
{
cnt=0;
for(int i=2;i<M;i++){
if(!f[i]) prime[cnt++]=i;
for(int j=0;j<cnt&&i*prime[j]<M;j++){
f[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
void solve(int m)
{
memset(dp,0,sizeof(dp));
for(int i=0;i<=n;i++) p[i]=1;
for(int i=0;i<cnt&&prime[i]<=n;i++){
double t=log(prime[i]);
for(int j=n;j>=prime[i];j--){
for(int k=prime[i],num=1;k<=j;k*=prime[i],num++)
if(dp[j-k]+t*num>dp[j]){
dp[j]=dp[j-k]+t*num;
p[j]=p[j-k]*k%m;
}
}
}
}
int main()
{
int m;
init();
while(scanf("%d%d",&n,&m)!=EOF){
solve(m);
printf("%d\n",p[n]);
}
return 0;
}

1. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。