首页 > 其他分享 >The Bells are Ringing UVA-12119

The Bells are Ringing UVA-12119

时间:2023-04-23 23:33:07浏览次数:46  
标签:lcm return Ringing int 12119 len printf UVA include

已知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

相关文章

  • UVA11014
     给定一个NxNxN的正方体,求出最多能选几个整数点。使得随意两点PQ不会使PQO共线。  F(k)#include<iostream>#include<cmath>#include<algorithm>usingnamespacestd;constintN=5e5;#defineintlonglongintb[N+2],pm[N+2],tot=0;intn;intpow3(intx){......
  • Gauss Prime UVA - 1415
     #include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;constintN=5e4;intb[N+2],pm[N+2],tot=0;voidinit(){b[1]=1;for(inti=2;i<=N;i++){if(b[i])continue;pm[++tot]=i;......
  • Counting Rectangles UVA - 10574
    给出n个点。问选出4个点作为定点,能够组成多少个平行与坐标轴的矩形。 点按照x排序 n^2挑选出垂直x轴的线段,按照y1排序  #include<iostream>#include<cstring>#include<algorithm>#include<vector>usingnamespacestd;constintN=1e5;structT{ intx......
  • Eigensequence UVA - 11133
    给你一个递增序列的第一位a1,最后一位an,求有多少个序列满足:以a1为首,an为尾 1、B(1)=A(1)2、后面每项满足A[j]=B[j], A(j-1)<B(j)≤A(j),且bj能整除A(j)-A(j-1)。   F[i][j]最后一位为j的方案数#include<iostream>#include<cstring>#include<a......
  • UVA Children’s Game(贪心)
    Description4thIIUCInter-University ProgrammingContest,2005AChildren’sGameInput:standardinputOutput:standardoutputProblemsetter: Md. KamruzzamanTherearelotsofnumbergamesforchildren.Thesegamesareprettyeasytoplaybutnotsoeasyt......
  • UVA Immediate Decodability(简单字典树)
    ImmediateDecodabilityTimeLimit:3000MS     MemoryLimit:0KB     64bitIOFormat:%lld&%lluSubmit StatusDescription  ImmediateDecodability Anencodingofasetofsymbolsissaidtobe immediately decodableifnocode......
  • UVA10237 Bishops
      #include<iostream>#include<cstring>#include<queue>usingnamespacestd;constintN=2e5+2;#defineintlonglongintn,m,f1[50][2000],f2[50][2000];voidsov(){ memset(f1,0,sizeoff1);memset(f2,0,sizeoff2); f1[0][0]=f2......
  • UVA How Many Points of Intersection?
      HowManyPointsofIntersection? a dotsonthetoprowand b dotsonthebottomrow.Wedrawlinesegmentsconnectingeverydotonthetoprowwitheverydotonthebottomrow.Thedotsarearrangedinsuchawaythatthenumberofinternalintersectio......
  • (UVA) The ? 1 ? 2 ? ... ? n = k problem
    The?1?2?...?n=kproblemTheproblemGiventhefollowingformula,onecansetoperators'+'or'-'insteadofeach'?',inordertoobtainagivenk?1?2?...?n=kForexample:toobtaink=12,theexp......
  • How Many O's? UVA - 11038
    写下区间[a,b]的所有数 ,问一共有多少个0 #include<iostream>#include<cstring>#include<vector>usingnamespacestd;#defineintlonglongintn,f[40][40][2][2];vector<int>a;intdfs(intx,intcnt0,intflg,intlead){ if(x<0){ i......