SRM 661 div1
Posted on 2015-06-13 18:41:40 +0900 in Contest
SRM 661 consists of 250 + 450 + 1000. 250 and 450 are two maths problems.
MissingLCM
Given $N \in [1,100000]$, find out the minimum $M \in (N, \infty)$ such that $lcm(1, 2, …, M)=lcm(N+1, N+2, …, M)$
Analyze
As $N$ is given, first consider how to calculate $lcm(1, 2, .., N)$
The answer would be only consider all the Prime number $P_i \in [1, N]$,
and find out the maximum $n_i$ such that
and
then the answer would be
So should have all the factors. The the answer would be
typedef long long LL;
class MissingLCM {
public:
bool isPrime[1000100];
int getMin(int N) {
if(N == 1){
return 2;
}
for(int i = 1; i <= N; ++i){
isPrime[i] = true;
}
for(int i = 2; i <= N; ++i){
if(isPrime[i] == false){
continue;
}
for(int j = 2 * i; j <= N; j += i){
isPrime[j] = false;
}
}
int ans = N;
for(int i = 2; i <= N; ++i){
if(isPrime[i] == false){
continue;
}
int temp = i;
while(temp <= N / i){
temp *= i;
}
ans = max(ans, (N / temp + 1) * temp);
}
return ans;
}
};ColorfulLineGraphs
Analyze
suppose $f[N][K]$ is the total number of using $K$ colors on $N$ nodes.
Now considering to build $f[N][K]$ from $f[N-1][K]$
For node $N$ choose whether to link to some node $i \in [1,N-1]$ or do not link at all.
- linked to some node $i$, there are $K - 1$ ways of color possibilities each.
- do not link to any other, there are $K$ ways of color possibilities.
So
The current time complexity is $O(n)$, which is not fast enough.
Notice $M$ is small, would be cyclic, $M$ would be one periodic according to Lagrange’s theorem
typedef long long LL;
#define REP(i, N) for (int i = 0; i < (int)N; i++)
struct ColorfulLineGraphs {
long long N;
long long K;
int M;
int fastPower(LL base, LL p){
int ans = 1;
for(LL cur = 0; ((LL)1<<cur) <= p; ++cur){
if(p & ((LL)1<<cur)){
ans = (ans * base) % M;
}
base = (base * base) % M;
}
return ans;
}
int countWays(long long _N, long long _K, int _M) {
N = _N, K = _K, M = _M;
LL ans = 1, res = 1;
K %= M;
for(LL cur = 1; cur <= M; ++cur){
res = (res * (cur * (K - 1) + 1)) % M;
if(N % M == cur){
ans = res;
}
}
ans = (ans * fastPower(res, N / M)) % M;
return ans;
}
};