題目鏈接:https://csacademy.com/contest/archive/task/gcd-rebuild/statement/
題目大意:給出一個N*M的矩陣,其中第i行j列表示gcd(a[i], b[j]),現在不知道數組a,b,給出這個矩陣,求a,b。如果多組解,輸出其中一組,若無解,輸出-1.
解題思路:觀察觀察(真的是觀察出來的),發現如果有解,那么可以按照如下方式構造解:
1 for(int i = 1; i <= n; i++){ 2 ll tmp = 1, la; 3 for(int j = 1; j <= m; j++){ 4 la = tmp; 5 tmp *= c[i][j]; 6 tmp /= gcd(la, c[i][j]); 7 } 8 a[i] = tmp; 9 }
對于每一列也是同樣的方式。構造之后判斷一下是否符合條件即可。
代碼:
1 const int maxn = 3e2 + 5; 2 int n, m; 3 ll c[maxn][maxn]; 4 ll a[maxn], b[maxn]; 5 6 ll gcd(ll x, ll y){ 7 return y == 0? x: gcd(y, x % y); 8 } 9 void solve(){ 10 for(int i = 0; i <= n; i++) c[i][0] = c[0][i] = 1; 11 bool flag = true; 12 for(int i = 1; i <= n; i++){ 13 ll tmp = 1, la; 14 for(int j = 1; j <= m; j++){ 15 la = tmp; 16 tmp *= c[i][j]; 17 tmp /= gcd(la, c[i][j]); 18 } 19 a[i] = tmp; 20 if(a[i] > 1e9) { 21 flag = false; 22 break; 23 } 24 } 25 if(!flag){ 26 puts("-1"); 27 return; 28 } 29 for(int i = 1; i <= m; i++){ 30 ll tmp = 1, la; 31 for(int j = 1; j <= n; j++){ 32 la = tmp; 33 tmp *= c[j][i]; 34 tmp /= gcd(c[j][i], la); 35 } 36 b[i] = tmp; 37 if(b[i] > 1e9) { 38 flag = false; 39 break; 40 } 41 } 42 if(!flag){ 43 puts("-1"); 44 return; 45 } 46 for(int i = 1; i <= n; i++){ 47 for(int j = 1; j <= m; j++){ 48 if(c[i][j] != gcd(a[i], b[j])){ 49 flag = false; 50 break; 51 } 52 } 53 if(!flag) break; 54 } 55 if(!flag){ 56 puts("-1"); 57 return; 58 } 59 for(int i = 1; i <= n; i++) printf("%lld ", a[i]); 60 puts(""); 61 for(int i = 1; i <= m; i++) printf("%lld ", b[i]); 62 } 63 int main(){ 64 scanf("%d %d", &n, &m); 65 for(int i = 1; i <= n; i++){ 66 for(int j = 1; j <= m; j++){ 67 scanf("%lld", &c[i][j]); 68 } 69 } 70 solve(); 71 }
題目:
Gcd Rebuild
Memory limit:?256 MB
Consider two arrays:?VV?of size?NN?and?UU?of size?MM. The elements of both arrays are integers between?11?and?10^910?9??.
You are given a matrix?AA?where?A_{i,j} = \gcd(V_i, U_j)A?i,j??=gcd(V?i??,U?j??)?and?\gcdgcd?refers to the greatest common divisor. You are asked to find?VV?and?UU.
Standard input
The first line contains two integers?NN?and?MM.
Each of the next?NN?lines contains?MM?integers, representing the elements of?AA.
Standard output
If there is no solution, or you cannot find a solution where the elements of?VV?and?UU?are in the range?[1, 10^9][1,10?9??], output?-1?1.
Otherwise, print the?NN?elements of?VV?on the first line and the?MM?elements of?UU?on the second line. If the solution is not unique you can output any of them.
Constraints and notes
- 1 \leq N, M \leq 3001≤N,M≤300?
- 1 \leq A_{i, j} \leq 10^91≤A?i,j??≤10?9???
Input | Output | Explanation |
---|---|---|
3 3 1 2 2 3 2 2 3 1 1 | 2 6 3 3 2 2 | gcd(2, 3)=1gcd(2,3)=1 gcd(2, 2)=2gcd(2,2)=2 gcd(6, 3)=3gcd(6,3)=3 gcd(6, 2)=2gcd(6,2)=2 gcd(3, 3)=3gcd(3,3)=3 gcd(3, 2)=1gcd(3,2)=1 |
3 2 2 2 2 2 4 2 | 2 2 4 4 2 | gcd(2, 2)=2gcd(2,2)=2 gcd(2, 4)=2gcd(2,4)=2 gcd(4, 4)=4gcd(4,4)=4 |
2 2 1 1 1 1 | 1 1 1 1 | gcd(1, 1)=1gcd(1,1)=1 |
3 3 4 2 4 2 4 2 4 2 4 | -1 | There is no solution |