結果

問題 No.373 かけ算と割った余り
コンテスト
ユーザー 半匠･鳳･みけねこ太郎
提出日時 2024-08-29 11:01:27
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 840 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 27,008 KB
実行使用メモリ 6,940 KB
最終ジャッジ日時 2024-08-29 11:01:30
合計ジャッジ時間 1,182 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
int main(){
long a,b,c,d;
    scanf("%ld%ld%ld%ld",&a,&b,&c,&d);

    a%=d;
    b%=d;
    c%=d;
    
    printf("%ld\n", ((a*b*c)%d));

    return 0;
}

/***********************************************************************************
(a1*a2*a3)%m mを法としたa1, a2, a3のmoduloをb1, b2, b3とおくと、
ある整数k1, k2, k3をおけばmoduloの定義式から
( (m*k1+b1)*(m*k2+b2)*(m*k3+b3) )%mである。

ここで、
(m*k1+b1)*(m*k2+b2)*(m*k3+b3)を展開すると、各項のうちmを含まない項はb1*b2*b3である。
よって、(a1*a2*a3)%mと(b1*b2*b3)*mは等しいため、
この問題におけるA, B, C各数のmoduloを取ってから掛け合わせ、
最後にmoduloを取ればよいと示せた。
***********************************************************************************/
0