SRM 599 DIV2 500p

原创: 2016-06-07 15:14:46678浏览

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<=sqrt(n);i+=2)
        if(n%i==0)return 0;
    return 1;
}
const int maxn=2e5+354;

struct data
{
    int a,b;
};
int p[maxn];
map 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<=ta;i++)
    {
        ll cnt=0;
        while(A%i==0)
        {
            cnt++;
            A/=i;
        }
        if(cnt)
            pa[i]=cnt*(ll)B;
    }

    if(A!=1ll)pa[A]=(ll)B;

    if(isp(C))
    {
        if(pa[C]
//Powered by [KawigiEdit] 2.0!