Codeforces1058 D. Vasya and Triangle(思维,数学)

题意:

Codeforces1058 D. Vasya and Triangle(思维,数学)

解法:

格 点 三 角 形 的 面 积 一 定 是 . 0 或 者 . 5 形 式 , 因 此 先 对 n ∗ m k 约 分 , 如 果 约 分 之 后 分 母 不 为 1 或 者 2 , 那 么 无 解 . n ∗ m k = ( 2 ∗ n ∗ m ) / k 2 , 显 然 该 式 的 结 果 是 整 数 那 么 问 题 变 为 找 到 一 个 格 点 矩 形 , 满 足 其 面 积 为 2 ∗ n ∗ m k . 设 矩 形 边 长 分 别 为 x 和 y , 那 么 x ∗ y = 2 ∗ n ∗ m k . 令 x = 2 ∗ n g c d ( 2 ∗ n , k ) , y = m k / g c d ( 2 ∗ n , k ) . 如 果 g c d ( 2 ∗ n , k ) = 1 , 那 么 x / = 2 , y ∗ = 2 即 可 . 容 易 证 明 这 样 做 之 后 x < = n 且 y < = m 一 定 成 立 . 格点三角形的面积一定是.0或者.5形式,\\ 因此先对\frac{n*m}{k}约分,如果约分之后分母不为1或者2,那么无解.\\ \frac{n*m}{k}=\frac{(2*n*m)/k}{2},显然该式的结果是整数\\ 那么问题变为找到一个格点矩形,满足其面积为\frac{2*n*m}{k}.\\ 设矩形边长分别为x和y,那么x*y=\frac{2*n*m}{k}.\\ 令x=\frac{2*n}{gcd(2*n,k)},y=\frac{m}{k/gcd(2*n,k)}.\\ 如果gcd(2*n,k)=1,那么x/=2,y*=2即可.\\ 容易证明这样做之后x<=n且y<=m一定成立. 格点三角形的面积一定是.0或者.5形式,因此先对kn∗m​约分,如果约分之后分母不为1或者2,那么无解.kn∗m​=2(2∗n∗m)/k​,显然该式的结果是整数那么问题变为找到一个格点矩形,满足其面积为k2∗n∗m​.设矩形边长分别为x和y,那么x∗y=k2∗n∗m​.令x=gcd(2∗n,k)2∗n​,y=k/gcd(2∗n,k)m​.如果gcd(2∗n,k)=1,那么x/=2,y∗=2即可.容易证明这样做之后x<=n且y<=m一定成立.

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,m,k;
void solve(){
    cin>>n>>m>>k;
    if(k/__gcd(n*m,k)>2){//不是.0或者.5形式,无解
        cout<<"NO"<<endl;
        return ;
    }
    cout<<"YES"<<endl;
    int x=n*2/__gcd(n*2,k);
    int y=m/(k/__gcd(n*2,k));
    if(__gcd(n*2,k)==1){
        x/=2,y*=2;
    }
    cout<<0<<' '<<0<<endl;
    cout<<x<<' '<<0<<endl;
    cout<<0<<' '<<y<<endl;

}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    solve();
    return 0;
}

上一篇:Cow Bowling


下一篇:杨辉三角:输入要打印的层数,打印杨辉三角。