[UOJ 48][UR #3]核聚变反应堆
转载请注明出处：http://danihao123.is-programmer.com/
先去考虑两个变量的sgcd怎么求……我们先求出他们的gcd，然后在除掉一个最小的质因子即可。
那么我们先把a1分解质因数，然后所有数和它求一个gcd，然后去去掉一个尽可能小的质因子。注意到一个数p的质因子数量是O(logp)级别的，所以每一个数找到要除的那个最小的质因子只需要O(loga1)的时间。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | #include <cstdio>#include <cstring>#include <cstdlib>#include <cctype>#include <algorithm>#include <utility>#include <vector>#include <cmath>const int maxn = 100005;using ll = long long;ll V[maxn]; int vcnt = 0;void des(ll x) { ll m = (ll)sqrt(x + 0.5); for(ll i = 2; i <= m; i ++) { if(x % i == 0) { V[vcnt ++] = i; while(x % i == 0) x /= i; } } if(x > 1LL) V[vcnt ++] = x;}ll gcd(ll a, ll b) { if(!b) return a; else return gcd(b, a % b);}ll A[maxn];int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i ++) { scanf("%lld", &A[i]); } des(A[1]); for(int i = 1; i <= n; i ++) { if(i > 1) putchar(' '); ll bs = gcd(A[i], A[1]); if(bs == 1) { printf("-1"); continue; } for(int j = 0; j < vcnt; j ++) { if(A[i] % V[j] == 0) { bs /= V[j]; break; } } printf("%lld", bs); } puts(""); return 0;} |
评论 (0)
