进入a b 多少努力p, q 使p*q == a && p < q && p >= b
直接大整数分解 然后dfs所有可能的解决方案劫持
#include#include #include #include #include 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;}
版权声明：本文博客原创文章。博客，未经同意，不得转载。