結果
| 問題 |
No.195 フィボナッチ数列の理解(2)
|
| コンテスト | |
| ユーザー |
 EmKjp
|
| 提出日時 | 2015-04-29 01:33:29 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,436 bytes |
| コンパイル時間 | 810 ms |
| コンパイル使用メモリ | 113,600 KB |
| 実行使用メモリ | 26,356 KB |
| 最終ジャッジ日時 | 2024-07-05 16:28:35 |
| 合計ジャッジ時間 | 2,204 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 WA * 9 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.IO;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Text;
partial class Solver {
/// <summary>
/// ax + by = p
/// cx + dy = q
/// </summary>
static bool CramersRule(long a, long b, long p, long c, long d, long q, out long x, out long y) {
x = 0; y = 0;
long det = a * d - b * c;
if (det == 0) return false;
long pdbq = p * d - b * q;
long aqpc = a * q - p * c;
if (pdbq % det != 0) return false;
if (aqpc % det != 0) return false;
x = pdbq / det;
y = aqpc / det;
return true;
}
public static void Swap<T>(ref T lhs, ref T rhs) { T temp; temp = lhs; lhs = rhs; rhs = temp; }
static public long ExtendedGcd(long a, long b, ref long x, ref long y) {
if (b == 0) {
x = 1; y = 0;
return a;
} else {
long d = ExtendedGcd(b, a % b, ref y, ref x);
y -= a / b * x;
return d;
}
}
static public bool ChineseRemainderTheorem(long a1, long m1, long a2, long m2,
ref long val, ref long mod) {
a1 %= m1; a2 %= m2;
if (a1 > a2) return ChineseRemainderTheorem(a2, m2, a1, m1, ref val, ref mod);
long A = 0, B = 0, g = ExtendedGcd(m1, m2, ref A, ref B);
if (a1 % g != a2 % g) return false;
long M = a1 % g;
a1 /= g; m1 /= g; a2 /= g; m2 /= g;
long k = (A + m2) * (a2 - a1) % m2;
mod = m1 * m2 * g;
val = ((a1 + k * m1) * g + M) % mod;
return true;
}
static public long Inverse(long a, long mod) {
long x = 0, y = 0;
if (ExtendedGcd(a, mod, ref x, ref y) == 1)
return (x + mod) % mod;
else
return -1;
}
public void Run() {
long X = nl();
long Y = nl();
long Z = nl();
if (X > Y) Swap(ref X, ref Y);
if (X > Z) Swap(ref X, ref Z);
if (Y < Z) Swap(ref Y, ref Z);
var fib = new List<long>();
fib.Add(0);
fib.Add(1);
while (true) {
var x = fib[fib.Count - 2] + fib[fib.Count - 1];
if (x > 2000000000) break;
fib.Add(x);
}
long ansA = -1, ansB = -1;
if (X == Y && Y == Z) {
for (int i = 0; i < fib.Count - 1; i++) {
long A = 0, B = 0;
// fib[i] * A + fib[i+1] * B = X
// B = (X - fib[i] * A) / fib[i+1]
// X - fib[i] * A = 0 (mod fib[i+1]
// fib[i] * A = X
// A = X * inv(fib[i]) mod fib[i+1]
A = X * Inverse(fib[i], fib[i + 1]) % fib[i + 1];
B = (X - fib[i] * A) / (fib[i + 1]);
if (A > 0 && B > 0) {
if (ansA == -1 || (ansA > A || (ansA == A && ansB > B))) {
ansA = A;
ansB = B;
}
}
}
} else {
for (int i = 0; i < fib.Count - 1; i++) {
for (int j = i; j < fib.Count - 1; j++) {
// fib[i] * A + fib[i+1] * B = X
// fib[j] * A + fib[j+1] * B = Y
long A, B;
if (CramersRule(fib[i], fib[i + 1], X, fib[j], fib[j + 1], Y, out A, out B)) {
if (A > 0 && B > 0) {
for (int k = 0; k < fib.Count - 1; k++) {
if (fib[k] * A + fib[k + 1] * B == Z) {
if (ansA == -1 || (ansA > A || (ansA == A && ansB > B))) {
ansA = A;
ansB = B;
}
}
}
}
}
}
}
}
if (ansA == -1) cout.WriteLine(-1);
else cout.WriteLine("{0} {1}", ansA, ansB);
}
}
// PREWRITEN CODE BEGINS FROM HERE
partial class Solver : Scanner {
public static void Main(string[] args) {
new Solver(Console.In, Console.Out).Run();
}
TextReader cin;
TextWriter cout;
public Solver(TextReader reader, TextWriter writer)
: base(reader) {
this.cin = reader;
this.cout = writer;
}
public Solver(string input, TextWriter writer)
: this(new StringReader(input), writer) {
}
public int ni() {
return NextInt();
}
public long nl() {
return NextLong();
}
public string ns() {
return Next();
}
}
public class Scanner {
private TextReader Reader;
private Queue<String> TokenQueue = new Queue<string>();
private CultureInfo ci = CultureInfo.InvariantCulture;
public Scanner()
: this(Console.In) {
}
public Scanner(TextReader reader) {
this.Reader = reader;
}
public int NextInt() { return Int32.Parse(Next(), ci); }
public long NextLong() { return Int64.Parse(Next(), ci); }
public double NextDouble() { return double.Parse(Next(), ci); }
public string[] NextArray(int size) {
var array = new string[size];
for (int i = 0; i < size; i++) array[i] = Next();
return array;
}
public int[] NextIntArray(int size) {
var array = new int[size];
for (int i = 0; i < size; i++) array[i] = NextInt();
return array;
}
public long[] NextLongArray(int size) {
var array = new long[size];
for (int i = 0; i < size; i++) array[i] = NextLong();
return array;
}
public String Next() {
if (TokenQueue.Count == 0) {
if (!StockTokens()) throw new InvalidOperationException();
}
return TokenQueue.Dequeue();
}
public bool HasNext() {
if (TokenQueue.Count > 0)
return true;
return StockTokens();
}
private bool StockTokens() {
while (true) {
var line = Reader.ReadLine();
if (line == null) return false;
var tokens = line.Trim().Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
if (tokens.Length == 0) continue;
foreach (var token in tokens)
TokenQueue.Enqueue(token);
return true;
}
}
}