Light OJ 1341 Aladdin and the Flying Carpet Pollard_rho整数分解+DFS

进入a b 多少努力p, q 使p*q == a && p < q && p >= b
直接大整数分解然后dfs所有可能的解决方案劫持
#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long LL;

const int Times = 25;

LL factor[100], f[100];

int l, ll, ans, num[100];

LL a, b;

LL gcd(LL a, LL b)

{

	return b ? gcd(b, a%b):a;

}

LL add_mod(LL a, LL b, LL n)

{

    LL ans = 0;

    while(b)

    {

        if(b&1)

            ans = (ans + a)%n;

        b >>= 1;

        a = (a<<1)%n;

    }

    return ans;

}

LL pow_mod(LL a, LL m, LL n)

{

    LL ans = 1;

    while(m)

    {

        if(m&1)

            ans = add_mod(ans, a, n);

        m >>= 1;

        a = add_mod(a, a, n);

    }

    return ans;

}

bool Witness(LL a, LL n)

{

    int j = 0;

    LL m = n-1;

    while(!(m&1))

    {

        j++;

        m >>= 1;

    }

    LL x = pow_mod(a, m, n);

    if(x == 1 || x == n-1)

        return true;

    while(j--)

    {

        x = add_mod(x, x, n);

        if(x == n-1)

            return true;

    }

    return false;

}

bool Miller_Rabin(LL n)

{

    if(n < 2)

        return false;

    if(n == 2)

        return true;

    if(!(n&1))

        return false;

    for(int i = 0; i < Times; i++)

    {

        LL a = rand()%(n-1)+1;

        if(!Witness(a, n))

            return false;

    }

    return true;

}

LL Pollard_rho(LL n, LL c)

{

	LL i = 1, x = rand()%(n-1)+1, y = x, k = 2, d;

	//srand(time(NULL));

	while(true)

	{

		i++;

		x = (add_mod(x,x,n)+c)%n;

		d = gcd(y-x,n);

		if(d > 1 && d < n)

			return d;

		if(y == x)

			return n;

		if(i == k)

		{

			y = x;

			k <<= 1;

		}

	}

}

void get_fact(LL n, LL k)

{

	if(n == 1)

		return;

	if(Miller_Rabin(n))

	{

		factor[l++] = n;

		return;

	}

	LL p = n;

	while(p >= n)

	{

		p = Pollard_rho(p, k--);

	}

	get_fact(p, k);

	get_fact(n/p, k);

}

void dfs(LL x, int p, LL m)

{

	if(x > m)

		return;

	if(p == ll)

	{

		if(x >= b && a/x > x)

			ans++;

		//printf("%lld\n", x);

		return;

	}

	LL y = 1;

	for(int i = 0; i <= num[p]; i++)

	{

		dfs(x*y, p+1, m);

		y *= f[p];

	}

}

int main()

{

	int cas = 1;

	int T;

	scanf("%d", &T);

	while(T--)

	{

		scanf("%lld %lld", &a, &b);

		LL m = sqrt(a+0.5);

		ans = 0;

		l = 0;

		get_fact(a, 120);

		sort(factor, factor+l);

		f[0] = factor[0];

		num[0] = 1;

		ll = 1;

		for(int i = 1; i < l; i++)

		{

			if(factor[i] != factor[i-1])

			{

				ll++;

				f[ll-1] = factor[i];

				num[ll-1] = 0;

			}

			num[ll-1]++;

		}

		//for(int i = 0; i < ll; i++)

		//	printf("%lld %d\n", f[i], num[i]);

		dfs(1, 0, m);

		printf("Case %d: %d\n", cas++, ans);

	}

	return 0;

}