Multiplication Table(Codeforces Round #586 (Div. 1 + Div. 2))

 题目链接:http://codeforces.com/contest/1220/problem/B

给你一个n*n的矩阵,m[i][j]=a[i]*a[j],让你求出a这个数列。

把矩阵用字符表达写出来,map[i][j]=a[i]*a[j];

就很好发现a[1]=sqrt(a[1][2]*a[1][3]/a[2][3]);

那么根据a[1]a[2],a[2][3],…,a[i][i+1],a[n-1][n]就可以求出a[2],a[3],…,a[I+1],a[n].
 

注意要关流,不然会超时

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define INF 0x3f3f3f3f
#define LL long long
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std;
LL map[1010][1010], a[1010];
int main()
{
	ios::sync_with_stdio(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> map[i][j];
	a[1] = sqrt(map[1][2] * map[1][3] / map[2][3]);
	cout << a[1] << ' ';
	for (int i = 1; i < n; i++)
	{
		a[i + 1] = map[i][i + 1] / a[i];
		cout << a[i + 1] << ' ';
	}
}
原文地址:https://www.cnblogs.com/shmilky/p/14089014.html