SRM599DIV2500p

Problem Statement This problem statement contains superscipts that may not display properly outside the applet. You are given four ints A , B , C and D . Return divisible (quotes for clarity) if A B is divisible by C D . Return not divisib

Problem Statement

This problem statement contains superscipts that may not display properly outside the applet.

You are given four ints A , B , C and D . Return "divisible" (quotes for clarity) if A B is divisible by C D . Return "not divisible" otherwise.

Definition

Class: BigFatInteger2 Method: isDivisible Parameters: int, int, int, int Returns: string Method signature: string isDivisible(int A, int B, int C, int D) (be sure your method is public)

Notes

- 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 (10 9 ), inclusive.

Examples

0)

6 

1 

2 

1 

Returns: "divisible" 

Here, A B = 6 1 = 6 and C D = 2 1 = 2. 6 is divisible by 2. 1)

2 

1 

6 

1 

Returns: "not divisible" 

2 is not divisible by 6. 2)

1000000000 

1000000000 

1000000000 

200000000 

Returns: "divisible" 

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

8 

100 

4 

200 

Returns: "not divisible" 

We can rewrite 8 100 as (2 3 ) 100 = 2 300 . Similarly, 4 200 = (2 2 ) 200 = 2 400 . Thus, 8 100 is not divisible by 4 200 . 4)

999999937 

1000000000 

999999929 

1 

Returns: "not divisible" 

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

2 

2 

4 

1 

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.

分解质因数。。。。

注意A或C可能是质数。。。。

#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);
};

typedef long long ll;
ll gcd(ll a,ll b)
{return b==0?a:gcd(b,a%b);}
bool isp(int n)
{
    if(n==2)return 1;
    if(n%2==0)return 0;
    for(int i=3;i  pa,pc;
string BigFatInteger2::isDivisible(int A, int B, int C, int D)
{
    string div("divisible"),nodiv("not divisible");

    ll a,b,c,d;
    a=A,b=B,c=C,d=D;
	int ta=sqrt(A),tc=sqrt(C);
    for(int i=2;i 
//Powered by [KawigiEdit] 2.0!
 

查看更多关于SRM599DIV2500p的详细内容...