Home > Article > Database > SRM 599 DIV2 500p

SRM 599 DIV2 500p

WBOYOriginal: 2016-06-07 15:14:461140browse

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⁹), inclusive.

Examples

Returns: "divisible"

Here, A^B = 6¹ = 6 and C^D = 2¹ = 2. 6 is divisible by 2.

Returns: "not divisible"

2 is not divisible by 6.

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.

Returns: "not divisible"

We can rewrite 8¹⁰⁰ as (2³)¹⁰⁰ = 2³⁰⁰. Similarly, 4²⁰⁰ = (2²)²⁰⁰ = 2⁴⁰⁰. Thus, 8¹⁰⁰ is not divisible by 4²⁰⁰.

999999937

1000000000

999999929

Returns: "not divisible"

Here A and C are distinct prime numbers, which means A^B 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.

分解质因数。。。。

注意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!

Statement：

The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Previous article：Oracle数据库基本知识及问题解决Next article：LINQ-to-SQL那点事~LINQ-to-SQL中的数据缓存与应对

See more