題目相關
題目鏈接
AtCoder Regular Contest 108 A 題，https://atcoder.jp/contests/arc108/tasks/arc108_a，
Problem Statement
Given are integers S and P. Is there a pair of positive integers (N,M) such that N+M=S and N×M=P?
Input
Input is given from Standard Input in the following format:
S P
Output
If there is a pair of positive integers (N,M)(N,M) such that N+M=SN+M=S and N×M=PN×M=P, print Yes; otherwise, print No.
Samples1
Sample Input 1
3 2Sample Output 1
YesExplaination
- For example, we have N+M=3 and N×M=2 for N=1,M=2.
Samples2
Sample Input 2
1000000000000 1
Sample Output 2
No
Constraints
- All values in input are integers.
題解報告
題目翻譯
給兩個正整數 S, P，問是否存在正整數 N 和 M，滿足 N+M=S 和 N*M=P，
題目分析
本題是一個比較簡單的數學題，根據題目的要求，我們已知 S 和 P，問是否存在 N 和 M，這樣，我們可以寫出兩個方程，
，這樣就是一個二元一次方程組，只需要求解這個方程組即可，使用換元法，我們零 M=S-N，帶入方程后得到，
，利用左手法則，整理后我們得到一個一元二次方程，
，這樣可以通過韋達定理來求解方程的跟，
根據韋達定理，可知 ，即
，根據一元二次方程求根公式，我們知道：
，方程有兩個虛數跟，本題不符合要求，
，方程有兩個相等整數跟，可能符合本題要求，
，方程有兩個不等的整數跟，可能符合本題要求，
根據一元二次方程求根公式，，根據題目提供的資料范圍我們知道 b=-S，而 S>0，因此 b>0 的，因此當
等于零時候，方程有兩個相等的正整數跟，當
，題目要求有兩個正整數跟，因此必須滿足
，也就是
即
才能有兩個正整數跟，
資料范圍估計
根據題目提供的資料范圍 ，我們在計算中需要使用到平方，也就是說，最大的資料為
，這說明超過了 unsigned long long 的范圍，哪么怎么辦？換一個更大的資料型別就可以了，最簡單的方法就是講所有資料當做 double 來處理，這樣就可以解決問題，
總結
本題的難度不大，但是細節比較多，
AC 參考代碼
//https://atcoder.jp/contests/arc108/tasks/arc108_a
//A - Sum and Product
#include <iostream>
#include <cmath>
using namespace std;
int main() {
double s,p;
cin>>s>>p;
//n+m=s m=s-n
//n*m=p n*(s-n)=p -n^2+s*n-p=0; n^2-s*n+p=0
//需要有兩個正整數跟，根據韋達定理, b^2-4ac，也就是
//s*s-4*1*p=s*s+4*p>0
double delta=s*s-4*p;
if (delta<0) {
//虛數根
cout<<"No\n";
} else if (0==delta) {
//相同根
cout<<"Yes\n";
} else {
//計算出根
double x=(s+sqrt(delta))/2;
double y=(s-sqrt(delta))/2;
if (y>0 && x+y==s && x*y==p) {
cout<<"Yes\n";
} else {
cout<<"No\n";
}
}
return 0;
}寫代碼的時候，用了比較笨的方法，直接將兩個跟計算出來，進行比較，
時間復雜度
O(1)，
空間復雜度
O(1)，
列舉
首先感謝 T_a_r_j_a_n 的評論，本題確實可以換一個思路，就是從 1 到 sqrt(P) 中列舉，是否存在資料滿足條件，為什么要開根號，因為我們有一個是乘積，N*M=P，
這里需要特別注意資料范圍問題，最大資料為 1e12，超過了 int 可以表示范圍，需要使用 long long 進行列舉，
而且使用列舉的方法，可以避免浮點數比較中頭大的精度問題，
AC 參考代碼
//https://atcoder.jp/contests/arc108/tasks/arc108_a
//A - Sum and Product
//從 1 到 sqrt(P) 中列舉是否存在 N 和 M，
#include <bits/stdc++.h>
using namespace std;
//如果提交到OJ，不要定義 __LOCAL
//#define __LOCAL
int main() {
#ifndef __LOCAL
//這部分代碼需要提交到OJ，本地除錯不使用
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#endif
long long s,p;
cin>>s>>p;
long long t=sqrt(p);
for (long long i=1; i<=t; i++) {
long long n=i;
long long m=s-i;
if (n*m==p) {
cout<<"Yes\n";
return 0;
}
}
cout<<"No\n";
#ifdef __LOCAL
//這部分代碼不需要提交到OJ，本地除錯使用
system("pause");
#endif
return 0;
}
時間復雜度
，其實就是
，
空間復雜度
O(1)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/226897.html
標籤：其他
下一篇：qt Android之環境建立