Codeforces 509 D. Restoring Numbers

http://codeforces.com/contest/509/problem/D

這題主要就是先把a和b陣列建構出來，因為要滿足 ( a(i) + b(j) ) % K == w(i,j) % K，所以可以推得K | abs( a(i) + b(j) – w(i,j) ) ，當K為所有 abs( a(i) + b(j) – w(i,j) ) 的因數時，由a和b構造出來的表格mod K後就會和原來的表格v一樣了。由於還要使K大於v裡所有的數，所以K可以直接取那些數的最大公因數，若v中有數大於等於K則無解。

輸出時要記得將a, b裡的數加上K之後再MOD K，這樣就可以避免為負數的情況。最後還要注意，如果a(i) + b(j) 都剛好等於 w(i,j) 時會發生什麼事呢?

Zerojudge d648: 國際象棋(knight)

分享一題有趣的題目~~~

題目來源: http://zerojudge.tw/ShowProblem?problemid=d648

題目大意: 象棋中的馬動法為「日」字形，也就是往一個方向動2步，往另一個方向動1步，我們已(2,1)表示。現在，定義一隻動法為(n,m)的馬，問你在足夠大的棋盤上，從棋盤左下角的格子出發，是否有辦法走到所有的棋盤格上?

 

這題我先用手模擬，畫累了QAQ於是乾脆打個程式，實際帶數字跑跑看，而經由推想之後得出結論，再去試著說明。