SRM 599 DIV2 500p

问题陈述 此问题陈述包含可能无法在小程序外部正确显示的超级脚本。给你四个整数 A 、 B 、 C 和 D 。如果 A B 可被 C D 整除，则返回可整除（为清楚起见，引号）。返回不可除

问题陈述 此问题陈述包含可能无法在小程序外部正确显示的超级脚本。
给定四个整数 、C 和 。如果 B 能整除，则返回“整除”（为清楚起见，加引号） D。否则返回“不可整除”。 可整除整数，整数，整数，整数返回：字符串方法签名： 笔记-、B、 和 1)

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)

A

、

B

D

A

C

定义

班级： BigFatInteger2 ^方法：

参数：

 

6

1

2

1

字符串 isDivisible(int A, int B, int C, int D)

（确保您的方法是公开的）

Returns: "divisible"

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

-返回值区分大小写。正整数 y 整除正整数 x 当且仅当存在正整数 z 使得 y*z=x。特别是，对于每个正整数 x，1 和 x 都会整除 x。约束

2

1

6

1

Returns: "not divisible"

-

2 is not divisible by 6.

A

C

D9 )，包含在内。示例0)

1000000000

1000000000

1000000000

200000000

将分别介于 1 和 1,000,000,000 之间 (10

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.

 

8

100

4

200

Returns: "not divisible"

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

这里，AB1 = 6 和 C = 21 = 2。6 能被 2 整除。

999999937

1000000000

999999929

1

Returns: "not divisible"

= 6

D

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

2

2

4

1

    2 不能被 6 整除。 2)     现在数字很大，但我们可以看到 AB 可以被整除 CD 来自 A=C 和 B>D. 3)     我们可以将 8100 重写为 (23)100 = 2300。同样，4200 = (22)200 = 2400。因此，8100 不能被 4200 整除。 4)     这里A和C是不同的素数，这意味着 AB 不能以 C 作为除数。 5)    

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 <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

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<int,ll> 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]<D)
            return nodiv;
    }

    for(int i=2;i<=tc;i++)
    {
        ll cnt=0;
        while(C%i==0)
        {
            cnt++;
            C/=i;
        }

        if(cnt)
        {
            if(pa[i]<(ll)cnt*D)
                return nodiv;
        }
    }
    return div;
}


//<%:testing-code%>
//Powered by [KawigiEdit] 2.0!