数学
問題リンク : https://icpcarchive.ecs.baylor.edu/external/63/6396.pdf問題概要 : 関数 f は2^63未満の正の整数 k を引数にとり、 k の素因数の異なるarrangementの数 n を返す関数である 例えば、 f(10) = 2 である なぜなら、 10 = 2 * 5 = 5 * 2 である…
問題リンク:https://icpcarchive.ecs.baylor.edu/external/65/6582.pdf問題概要: 長さn(1 数列の各要素a[i]は1以上10^12以下 数列の連続した部分列を取り出し、(部分列全体のgcd) * (部分列の長さ) を値とする 値の最大値を出力せよ解法: 部分列の最も右と…
問題リンク : http://uva.onlinejudge.org/external/114/11401.pdf問題概要 : 3以上の整数 n が与えられたとき、 長さが1からnまでの棒がそれぞれ1本ずつあるものとして それらのうち3本を選んで作れる三角形の個数を出力せよ n が3未満ならばプログラムを終…
問題概要: これまた備忘録なので略解法: 1からNまでの周期が存在するので(<=ノートに書いてたらそんな感じ、直感的に) 1からNまでの最小公倍数を求めれば良い(<=さっきのことがわかればそうなるでしょうね) 1からNまでで存在する素数を列挙し…
問題リンク : http://uva.onlinejudge.org/external/127/12708.pdf問題概要 : 正の整数Nが与えられる。 N以下の任意の異なる2つの正の整数を選び、その最大公約数を求める こうして得られる最大公約数のうち、最大のものを出力せよ解法 : Nが偶数のとき、N/…
問題リンク:2603 -- Brave balloonists問題概要: 1以上10000以下の整数が10個与えられる これらの積の約数の数の最後の桁を出力せよ解法: 10個の整数をそれぞれ素因数分解し、各素因数の数を数える あとはそれらの数の積をとり、最後の一桁だけ出力するコ…
問題リンク:2661 -- Factstone Benchmark問題概要: とある会社が1960年に4-bitコンピュータをリリースした 1970年には8-bit,1980年には16-bit,.... といった感じで、10年毎にbit数が2倍になっていく ある年y( 1960 その年のコンピュータがunsigned intで表…
問題リンク : http://uva.onlinejudge.org/external/105/10577.html問題概要 : 正多角形のうち3点だけが与えられる その3点から本来の正多角形を復元し、その正多角形を囲むようなx軸とy軸に平行な長方形の面積の最少値を求めよ解法 : 正n角形の中心点が分…
問題リンク:http://uva.onlinejudge.org/external/104/10445.html問題概要: 多角形が与えられる その多角形の連続する3点からなる角度の最大と最小を求めよ解法: 全ての角度をみてその中の最大と最小を求める 入力は時計回りで与えられるのか反時計回りで…
問題リンク:http://uva.onlinejudge.org/external/115/11505.html問題概要: 略解法: その通りにシュミレーションする 出力する際に(int)round(sqrt(x*x+y*y))のように (int)でキャストしないとWAになる もしくはepsをつけるコード: #include<iostream> #include<cmath> #d</cmath></iostream>…
問題リンク:http://uva.onlinejudge.org/external/106/10637.html問題概要: 整数Sをt個のco-primeな値に分割したものを全て出力せよ解法: dfsで枝刈りしながら探索した brute forceな感じが。。。(正しくは素数使ってなんたらららしい) 全探索する過程…
問題リンク:http://uva.onlinejudge.org/external/105/10520.html問題概要: 短いので略解法: 式に従って頑張ってノートでシュミレーションして見た結果左したのあたりから戻るように埋めていくとよさそう・・・だがしかし今回nが20しかないので、 最大20*…
問題リンク:http://uva.onlinejudge.org/external/110/11054.html問題概要: n人の人がワインを売買する 人iの情報はa[i](0= 0 ならその人はa[i]個のワインを買う a[i] a[i]の総和は0となる a[i]のうち任意の数を任意の場所に移動できる その際に、abs(j-i…
問題リンク:http://uva.onlinejudge.org/external/113/11326.html問題概要: H*Wの部屋がある 壁は全て鏡である 部屋の左下からレーザービームを角度thetaで打つ そのレーザービームは部屋の右の壁のある一点にぶつかる その時のレーザービームの長さAと直…
問題リンク:Power of Cryptography問題概要: n,p (p k^n = p となるような k を求めよ(k 解法: pがかなり大きいが、doubleでなんとかなるみたいk^n = p より k = n√p (つまり、p^(1/n)) または k^n = p より log(k)p = n log p/log k = n log p = n log k…
問題リンク;Fermat vs. Pythagoras問題概要: あるpositive integer Nが与えられる x,y,zをN以下のpositive integersとする x*x + y*y = z*z を満たす様なx,y,zの組の内、x,y,zのそれぞれが互いに素なものの数と、x*x+y*y = z*z を満たすようなx,y,zでないN…