SRM 599 div2 250 500 - JAVA

- The return value is case-sensitive. - Positive integer y divides a positive integer x if and only if there is a positive integer z such that y*z=x. In particular, for each positive integer x, both 1 and x divide x.

Constraints

- A, B, C and D will each be between 1 and 1,000,000,000 (109), inclusive.

Examples

Returns: "divisible"

Here, AB = 61 = 6 and CD = 21 = 2. 6 is divisible by 2.

Returns: "not divisible"

2 is not divisible by 6.

1000000000

200000000

Returns: "divisible"

Now the numbers are huge, but we can see that AB is divisible by CD from the fact that A=C and B>D.

100

200

Returns: "not divisible"

We can rewrite 8100 as (23)100 = 2300. Similarly, 4200 = (22)200 = 2400. Thus, 8100 is not divisible by 4200.

999999937

1000000000

999999929

Returns: "not divisible"

Here A and C are distinct prime numbers, which means AB cannot have C as its divisor.

Returns: "divisible"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

#include 
  
   
#include 
   
     #include 
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include 
                
                  #include 
                 
                   #include 
                  
                    #include 
                   
                     using namespace std; class BigFatInteger2 { public: string isDivisible(int, int, int, int); }; string BigFatInteger2::isDivisible(int A, int B, int C, int D) { string div("divisible"),nodiv("not divisible"); map
                    
                      primeA,primeB; int ta=sqrt(A),tc=sqrt(C); for(int i=2;i<=ta;i++) { long long int cnt=0; while(A%i==0) { A/=i; cnt++; } if(cnt) { primeA.insert(make_pair(i,(long long )cnt*B)); } } if(A!=1LL) primeA.insert(make_pair(A,(long long )B)); bool flag=true; for(int i=2;i<=tc;i++) { long long int cnt=0; while(C%i==0) { C/=i; cnt++; } if(cnt) { if(primeA.count(i)==0) { flag=false;break; } else if(primeA[i]<(long long )D*cnt) { flag=false;break; } } } if(C!=1LL&&flag) { if(primeA.count(C)==0||primeA[C]
                     
                       //Powered by [KawigiEdit] 2.0! //<%:start-tests%>

SRM 599 div2 250 500(二)

Constraints

Examples