題目
分析：枚舉最大數，然后找出它所有因數p1…….pk， 從中任意選取一些數，這些數的LCM|這個數且，這些數的最大LCM就是枚舉的這個數，且若pi<=aj<=pi+1則前i個數可以放在j這個位置，即j這個位置有cj種選擇，總方案數就是c1*c2*……*cj
作為優化，對于每個pi，我們枚舉有aj滿足pi<=aj<=pi+1的個數記為qi，則有ans=1^qi*2^qi*……*q^qk，但這些方案包含不選擇最大數的情況，則最后一項應為q^qk-(q-1)^qk

代碼：

#include<cstdio> #include<algorithm> #include<cmath> using namespace std; #define MAXN 100000 #define MOD 1000000007 long long a[MAXN+10],n,p[MAXN+10],cnt,ans; void Read(long long &x){char c;while((c=getchar())&&c!=EOF){if(c>='0'&&c<='9'){x=c-'0';while((c=getchar())&&c>='0'&&c<='9')x=x*10+c-'0';ungetc(c,stdin);return;}} } void isfactor(long long n){long long t=sqrt(n+0.5),i;cnt=0;for(i=1;i<=t;i++)if(n%i==0)p[++cnt]=i;i=cnt;cnt*=2;if(t*t==n)cnt--,i--;for(;i;i--){p[cnt-i+1]=n/p[i];} } long long pow(long long a,long long b){long long ret=1;while(b){if(b&1)ret=ret*a%MOD;b>>=1;a=a*a%MOD;}return ret; } int main() {long long i,j,k,t,s;Read(n);for(i=1;i<=n;i++)Read(a[i]);sort(a+1,a+n+1);for(i=1;i<=a[n];i++){isfactor(i);t=0;s=1;for(j=2;j<=cnt;j++){k=lower_bound(a+t+1,a+n+1,p[j])-a-1;s=s*pow(j-1,k-t)%MOD;t=k;}s=s*(pow(cnt,n-t)+MOD-pow(cnt-1,n-t))%MOD; //cnt^n-t%MOD有可能cnt-1^n-t%MOD小ans=(ans+s)%MOD;}printf("%I64d\n",ans); }

轉載于:https://www.cnblogs.com/outerform/p/5921946.html

總結

以上是生活随笔為你收集整理的【数论】[CF258C]Little elephant and LCM的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。