CS Academy Gcd Rebuild

題目鏈接: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

Time limit:?1000 ms
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 3001N,M300?
  • 1 \leq A_{i, j} \leq 10^91A?i,j??10?9???
InputOutputExplanation
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

轉載于:https://www.cnblogs.com/bolderic/p/7500447.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/282439.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/282439.shtml
英文地址,請注明出處:http://en.pswp.cn/news/282439.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

ASP.NET Core 在 IIS 下的兩種部署模式

KestrelServer最大的優勢體現在它的跨平臺的能力&#xff0c;如果ASP.NET CORE應用只需要部署在Windows環境下&#xff0c;IIS也是不錯的選擇。ASP.NET CORE應用針對IIS具有兩種部署模式&#xff0c;它們都依賴于一個IIS針對ASP.NET CORE Core的擴展模塊。一、ASP.NET CORE Cor…

navicat連接遠程mysql

環境介紹: 這里,我連接的是阿里云的服務器,自己搭的環境,用的是mysql 5.7一 首先第一步,需要進入遠程服務器的mysql,更改host訪問權限 然后,將root允許訪問的host 改為%(任何ip地址都可以訪問) 注: 原來是只允許本地訪問二 本地用navicat連接遠程mysql 1. 常規部分填寫2. SSH部…

2018-08-15期 HBase命令行使用案例

1、進入hbase命令行[roothadoop-server01 bin]# hbase shell2、命令行幫助COMMAND GROUPS:Group name: generalCommands: status, table_help, version, whoamiGroup name: ddlCommands: alter, alter_async, alter_status, create, describe, disable, disable_all, drop, dro…

面向對象五大設計原則

最近在看七牛云許式偉的架構課, 重溫了面向對象五大設計原則(SOLID)&#xff0c;扣理論文字找出處。&#xff08;當然許老板是不可能深聊這么低級的內容&#xff0c;&#x1f921;&#xff09;注意區分設計原則和設計模式。設計原則更為抽象和泛化&#xff1b;設計模式也是抽象…

python函數式編程-匿名函數

>>> map(lambda x: x * x, [1, 2, 3, 4, 5, 6, 7, 8, 9]) [1, 4, 9, 16, 25, 36, 49, 64, 81] 關鍵字lambda表示匿名函數&#xff0c;冒號前面的x表示函數參數。 匿名函數有個限制&#xff0c;就是只能有一個表達式&#xff0c;不用寫return&#xff0c;返回值就是該表…

bean初始化、注銷

關于在spring 容器初始化 bean 和銷毀前所做的操作定義方式有三種&#xff1a; 第一種&#xff1a;通過PostConstruct 和 PreDestroy 方法 實現初始化和銷毀bean之前進行的操作 第二種是&#xff1a;通過 在xml中定義init-method 和 destory-method方法 第三種是&#xff1a;…

谷歌F12調試公眾號時,讓鼠標顯示出來

yi 環境介紹: win10 , 谷歌瀏覽器yii 概述: 在項目中,需要調試公眾號,本地環境搭好之后,在谷歌瀏覽時,發現移動到公眾號區域,鼠標居然不見了,這讓我怎么操作?各種操作可謂是日了狗了,非常麻煩yiii 調試時鼠標不見的解決辦法: 網上各種說法眾說紛紜,這里,我給出本人認為最恰當簡…

利用bootstrap插件設置時間

$("#"id_rand" .shijian-input").each(function () { $(this).datetimepicker({ lang:"ch", //語言選擇中文 注&#xff1a;舊版本 新版方法&#xff1a;$.datetimepicker.setLocale(ch); format: "hh : ii", /…

C# 編寫的 64位操作系統 -MOOS

MOOSMOOS ( My Own Operating System )是一個使用.NET Native AOT技術編譯的C# 64位操作系統。項目地址&#xff1a;https://github.com/nifanfa/MOOS編譯關于編譯MOOS的信息&#xff0c;請閱讀 編譯維基頁面&#xff1a;https://github.com/nifanfa/MOOS/wiki/。編譯要求VMwar…

js獲取屏幕寬高和下拉加載更多

document.body.clientWidth > BODY對象寬度 document.body.clientHeight > BODY對象高度 document.documentElement.clientWidth > 可見區域寬度 document.documentElement.clientHeight > 可見區域高度 網頁可見區域寬&#xff1a; document.body.clientWid…

X5開發中buttongrounp對應contents組件切換時速度快點無效

官方提供的解決辦法是&#xff1a;http://docs.wex5.com/wex5-ui-question-list-2084/ 原文如下&#xff1a;【問題】buttongrounp中的button按鈕全是代碼動態生成&#xff0c;對應的contents中的content也是代碼動態生成。發現在快讀點擊button的時候&#xff0c;content就會死…

JAVA語言基礎-面向對象(IO:IO字符流、遞歸)

2019獨角獸企業重金招聘Python工程師標準>>> 21.01_IO流(字符流FileReader) 1.字符流是什么 字符流是可以直接讀寫字符的IO流字符流讀取字符, 就要先讀取到字節數據, 然后轉為字符. 如果要寫出字符, 需要把字符轉為字節再寫出.2.FileReader FileReader類的read()方法…

windows下, nginx 提示錯誤 No input file specified

一 環境介紹: win10, LNMP 二 錯誤描述: 訪問網站時,提示"No input file specified"錯誤. 排錯階段: 1. 查看nginx access日志 (access.log) 發現提示404 錯誤 2. 分析原因: 這時,在同目錄下創建一個txt文件,訪問就可以正常輸出了 這說明 現在nginx 訪問php 沒…

Ubuntu20.04+docker+jenkins+飛書實現自動化發布

一、從0-1一點一滴實現如何本地提交代碼到gitlab然后實現前后端自動發布1.更新apt包索引sudo apt-get update2.安裝必備的軟件包以允許apt通過https使用存儲庫sudo apt-get install ca-certificates curl gnupg lsb-release3.添加Docker官方版本的GPG密鑰sudo mkdir -p /etc/ap…

一個Demo讓你掌握Android所有控件

一個Demo讓你掌握Android所有控件 原文:一個Demo讓你掌握Android所有控件本文是轉載收藏,侵刪,出處:"安卓巴士" 下面給出實現各個組件的源代碼&#xff1a; 1.下拉框實現--Spinner [java] view plaincopyprint?package com.cellcom; import java.util.ArrayList;…

九妹帶你走向 架構師

邁向系統架構師編者按&#xff1a;系統架構師是許多程序員的夢想職業。今天的你也許已經掌握了各種開發工具&#xff0c;并且能夠使用各種平臺進行開發&#xff0c;但作為一個架構師的要求&#xff0c;也許還有很長的道路。邢波濤先生在LAMP架構上的造詣&#xff0c;讓我邀請他…

WPF 使用 DrawingContext 繪制溫度計

WPF 使用 DrawingContext 繪制溫度計控件名&#xff1a;Thermometer作者&#xff1a; WPFDevelopersOrg原文鏈接&#xff1a; https://github.com/WPFDevelopersOrg/WPFDevelopers框架使用大于等于.NET40&#xff1b;Visual Studio 2022;項目使用 MIT 開源許可協議&#xff…

MAVEN簡介之——settings.xml

概述 Maven的settings.xml配置了Maven執行的方式&#xff0c;像pom.xml一樣&#xff0c;但是它是一個通用的配置&#xff0c;不能綁定到任何特殊的項目。它通常包括本地倉庫地址&#xff0c;遠程倉庫服務&#xff0c;認證信息等。 settings.xml存在于兩個位置&#xff1a; mave…

裝win10系統

一、使用U盤介質安裝win10系統&#xff08;官方方式&#xff09; 官方安裝工具下載地址&#xff1a;https://www.microsoft.com/zh-cn/software-download/windows10 1、進入官方安裝工具下載頁面&#xff0c;點擊立即下載工具&#xff0c;下載安裝工具。2、下載完成后&#xff…

C#構造函數、操作符重載以及自定義類型轉換

構造器 構造器&#xff08;構造函數&#xff09;是將類型的實例初始化的特殊方法。構造器可分為實例構造器和類型構造器&#xff0c;本節將詳細介紹有關內容。 實例構造器 顧名思義&#xff0c;實例構造器的作用就是對類型的實例進行初始化。如果類沒有顯示定義任何構造器&…