D. Restoring Numbers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Vasya had two arrays consisting of non-negative integers:aof sizenandbof sizem. Vasya chose a positive integerkand created ann×mmatrixvusing the following formula:
Vasya wrote down matrixvon a piece of paper and put it in the table.
A year later Vasya was cleaning his table when he found a piece of paper containing ann×mmatrixw. He remembered making a matrix one day by the rules given above but he was not sure if he had found the paper with the matrixvfrom those days. Your task is to find out if the matrixwthat you’ve found could have been obtained by following these rules and if it could, then for what numbersk,a1,a2,…,an,b1,b2,…,bmit is possible.
Input
The first line contains integersnandm(1≤n,m≤100), separated by a space — the number of rows and columns in the found matrix, respectively.
Thei-th of the following lines contains numberswi,1,wi,2,…,wi,m(0≤wi,j≤109), separated by spaces — the elements of thei-th row of matrixw.
Output
If the matrixwcould not have been obtained in the manner described above, print "NO" (without quotes) in the single line of output.
Otherwise, print four lines.
In the first line print "YES" (without quotes).
In the second line print an integerk(1≤k≤1018). Note that each element of tablewshould be in range between0andk-1inclusively.
In the third line printnintegersa1,a2,…,an(0≤ai≤1018), separated by spaces.
In the fourth line printmintegersb1,b2,…,bm(0≤bi≤1018), separated by spaces.
Sample test(s)
input
2 31 2 32 3 4
output
YES10000000070 1 1 2 3
input
2 21 22 0
output
YES30 1 1 2
input
2 21 22 1
output
NO
Note
Bywe denote the remainder of integer division ofbbyc.
It is guaranteed that if there exists some set of numbersk,a1,…,an,b1,…,bm, that you could use to make matrixw, then there also exists a set of numbers that meets the limits1≤k≤1018,1≤ai≤1018,1≤bi≤1018in the output format. In other words, these upper bounds are introduced only for checking convenience purposes.
/** * Created by ckboss on 15-4-2. */import java.util.*;public class CF509D {int n,m;long[][] w;long[] a,b;long gcd(long a,long b){if(b==0) return a;return gcd(b,a%b);}CF509D(){Scanner in = new Scanner(System.in);n=in.nextInt(); m=in.nextInt();w=new long[n][m];a=new long[n];b=new long[m];for(int i=0;i<n;i++)for(int j=0;j<m;j++) {w[i][j] = in.nextLong();}for(int i=0;i<m;i++) b[i]=w[0][i];for(int i=1;i<n;i++) a[i]=w[i][0]-b[0];long g=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){long c = Math.abs(a[i]+b[j]-w[i][j]);g=gcd(g,c);}}if(g==0) g=10000000007L;boolean flag=true;for(int i=0;i<n&&flag;i++) {for(int j=0;j<m;j++){if(w[i][j]>=g){flag=false; break;}}}if(flag==false){System.out.println("NO");}else{System.out.println("YES");System.out.println(g);for(int i=0;i<n;i++)System.out.printf("%d%c",(a[i]+g)%g,(i==n-1)?'\n':' ');for(int i=0;i<m;i++)System.out.printf("%d%c",(b[i]+g)%g,(i==m-1)?'\n':' ');}}public static void main(String[] args){new CF509D();}}
，勇于接受自己的失败，告诉自己，这就是自己的现实，
