#Div.1

##Level 1.MissingLCM

###Task

定义\(lcm(a_1,a_2,\ldots,a_n)\)为\(a_1,a_2,\ldots,a_n\)的最小公倍数,给定正整数\(N\),求最小的\(M\)使得\(lcm(N+1,N+2,\ldots,M) = lcm(1,2,\ldots,M)\)

###Solution

最大公倍数由质因数的最大倍数决定，枚举质数\(p\)，找到\(1.. N\)之间它的次数最大的项，便能算出下一次因数这么大或比它还大的时候(\(p(\left[\frac{N}{kp}\right]+1)\))

###Code

class MissingLCM {
    public:
        const int maxn = 1000000+5;
        int getMin(int N)
        {
            bool prime[maxn];
            int ans=N+1;
            memset(prime,-1,sizeof(prime));
            for (int i=2;i<=N;i++)
            {
                if (prime[i])
                {
                    long long p=i;
                    for (int j=i+i;j<=N;j+=i) prime[j]=0;
                    while (p*i <= N) p*=i;
                    ans=max((long long)ans,p*(N/p+1));
                }
            }
            return ans;
        }
};

##Level2 ColorfulLineGraphs

Bob is going to create a graph with N nodes. The graph will be constructed in two steps. First, Bob will take N isolated vertices, label them 1 through N and color each of them using one of K colors. Then, Bob will add some directed edges to the graph. For each i between 2 and N, inclusive, Bob may choose a single value j < i such that the nodes i and j have different colors. If he does, he will add the edge from i to j to his graph. Note that Bob may choose not to add any edge from node i, even if there are some valid choices of j.

Two graphs are considered the same if they have the same node colors and the same set of edges.

You are given the longs N and K. You are also given an int M. Compute and return the number of different graphs Bob may construct, modulo M.

###Solution

对于第i个点,假设它前面颜色p出现了\(c_p\)次,由DP的思想,我们知道到对第i个点,图的种数有\(f(x)=\Sigma_{j=1}^k ((i-1)-c_j+1) = k(i-1)-(i-1)+k = k+(i-1)(k-1)\)种

接着,我们发现,因为答案要对M取模,所以i=1和i=M+1的结果一样,故答案可以用\(f(M)^{\left[\frac{N}{M}\right]}f(N\mod M)\)求出来

###Code

class ColorfulLineGraphs{
    public:
        long long N,K,M;
        long long calc(long long x)
        {
            long long ret=1;
            for (int i=0;i<x;i++)
                (ret*=(K+i*(K-1))%M)%=M;
            return ret;
        }
        long long pow(long long a,long long b)
        {
            long long ret=1,tmp=a;
            while (b)
            {
                if (b&1) (ret*=tmp)%=M;
                (tmp*=tmp)%=M;
                b>>=1;
            }
            return ret;
        }
        int countWays(long long _n,long long _k,long long _m)
        {
            N=_n;K=_k;M=_m;
            return (int)((pow(calc(M),(N/M))*calc(N%M))%M);
        }
};

##Level3