已知M 为T1,T2,T3 的LCM
输出满足 Ti-Tj<=25 的所有可能情况
#include<iostream> #include<cmath> #include<algorithm> #include<cstring> using namespace std; const int N= 1E6+3; #define int long long int pm[N],tot; int b[N],fac[N],F[N],len,cnt[N]; int n,T; void init(int top){ tot=0; b[1]=1; for(int i=2;i<=top;i++){ if(b[i]) continue; pm[++tot]= i; for(int j=2;j*i<=top;j++) b[j*i]=1; } } void divide(int x){ len=0; memset(cnt,0,sizeof cnt); for(int i=1;i<=tot;i++){ if(x%pm[i]==0){ fac[++len]=pm[i] ; while(x%pm[i]==0) cnt[len]++, x/=pm[i]; } } if(x>1){ fac[++len]=x; cnt[len]=1; } } int gcd(int x,int y){ return y==0?x:gcd(y,x%y); } int lcm(int x,int y){ return x/gcd(x,y)*y; } void dfs (int d, int u) { if (u > 1000000LL) return; if (d>len) { F[++T] = u; return; } for (int i = 0; i <= cnt[d]; i++) { dfs(d+1, u); u *= fac[d]; } } signed main () { int cas =0; init(1e6) ; while (scanf("%lld",&n)==1&&n) { int ok=0; T=0; printf("Scenario %d:\n", ++cas); divide(n); dfs(1,1); sort(F+1,F+1+T); for (int i=1;i<=T;i++) { for (int j=i+1; j<=T; j++) { if (F[j]-F[i]>25) break; int d =lcm(F[i],F[j]); for (int k=j+1;k<=T;k++) { if (F[k]-F[i]>25) break; if (lcm(d,F[k]) == n) { printf("%d %d %d\n", F[i],F[j],F[k]); ok=1; } } } } if(ok == 0) printf("Such bells don't exist\n"); printf("\n"); } }
标签:lcm,return,Ringing,int,12119,len,printf,UVA,include From: https://www.cnblogs.com/towboa/p/17348126.html