競技プログラミング メモ【数学関連】【C#】

競技プログラミングで問題を解く上で必要な数式や性質についてまとめます。

数学

剰余の性質

・で割った余りを求めよ〜などで使えます。

下記の例の場合、引数nが非常に大きい場合、をすることにより、longの64bitに収まらず、オーバーフローしてしまう場合があります。そのため、都度余りを求めるのが無難です。

public static long Factorial(int n){
       if(n==0){
         return 1L;
     }else{
          return n * Factorial(n-1)%(1000000000+7);
      }
 }

二元一次不定方程式の整数解

を満たす整数解x,yは存在するのか、という問題です。
これを求めるためには、式変形を行い、
が整数であることを考えれば良いです。
しかし、この不明な整数yが必要になるので求められません。
そこで、不定方程式の整数解についての定理が活用できます。

そのため、これをプログラムで求めるには最大公約数を先に求める必要があります。

最大公約数

public static float Gcd(float a, float b){
            float x = 0;
            while(true){
                if(a%b==0){
                    return b;
                }else{
                    x = a % b;
                    a = b;
                    b = x;
                }
            }
        }

ちなみに、

最小公倍数

public static float Lcm(float a, float b)
{
        var x = Gcd(a, b);

        return a * b / x;
}

桁数18乗程度の場合のあまりの計算(ulong)

string[] line = 
Console.ReadLine().Trim().Split(' ');
var a = ulong.Parse(line[0]);
var b = ulong.Parse(line[1]);
Console.WriteLine(Math.Min(a%b,(a+b)/b*b-a));

平方根を用いた式の比較時

・両辺を２乗した場合の比較結果も考慮する
など
※誤差により、誤った判定を行う場合があります。