topcoder srm 661 div1 -3-白红宇

topcoder srm 661 div1 -3

阅读量：6829 次

发布时间：2019-06-26

本文共 1731 字，大约阅读时间需要 5 分钟。

1、给出一个$N$，求一个大于$N$且最小的数字$M$，使得$lcm(1,2,..,N)$=$lcm(1,2,...,M)$

思路：$N+1$到$M$ 之间的数字要包含所有1到$N$之间出现的质因子及其最高幂即可。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;int prime[1000005],tag[1000005];int pNum;void init(int n) { for(int i=2;i<=n;++i) if(!tag[i]){ prime[++pNum]=i; for(int j=i+i;j<=n;j+=i) tag[j]=1; }}class MissingLCM{public: int getMin(int N) { if(N==1) return 2; init(N); int ans=0; for(int i=1;i<=pNum;++i) { int t=1; while((long long)t*prime[i]<=N) { t*=prime[i]; } int tmp=N%t==0?N+t:(N/t+1)*t; if(tmp>ans) { ans=tmp; } } return ans; }};

2、

思路：从第一个节点到第$N$个节点依次考虑。对于第$i$个节点来说，分别枚举其颜色：

（1）颜色为0时，可以选择不连边，或者连边，方案数为$1+i-1-cal(i-1,0)$，其中$cal(x,y)$ 表示前$x$个节点中，颜色为$y$ 的节点的个数；

（2）颜色为1时，$1+i-1-cal(i-1,1)$

（3）颜色为$t$时，$1+i-1-cal(i-1,t)$

（4）颜色为$K$时，$1+i-1-cal(i-1,K)$

所以节点$i$的方案数为$f(i)=\sum_{t=1}^{K}(1+i-1-cal(i-1,t))=K*i-\sum_{t=1}^{K}cal(i-1,t)=K*i-(i-1)=K+(K-1)(i-1)$。

所以最后的答案为:

$ans=\prod_{i=1}^{N}f(i)$

$=\prod_{i=1}^{N}(K+(K-1)(i-1))$

$=\prod_{i=0}^{N-1}(K+(K-1)i)$

$=\prod_{j=0}^{min(M-1,N-1)}(K+(K-1)j)^{\frac{N-1-j}{M}+1}$

最后一步是由于$[1,N]$之间的数字模$M$会出现循环。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;int Pow(long long x,long long y,int M) { x%=M; int ans=1; while(y) { if(y&1) ans=(long long)ans*x%M; x=x*x%M; y>>=1; } return ans;}class ColorfulLineGraphs{public: int countWays(long long N,long long K,int M) { int ans=1; for(int i=0;i