こんにちはキキ&&http://acm.hdu.edu.cn/showproble_PHP チュートリアル
- WBOYオリジナル
- 2016-07-13 17:52:261206ブラウズ
問題の説明
ある日、私はスーパーで買い物をしていました。レジ係が真剣に小銭を数えていると、小さな子供が「门前大桥下游过一群鸭、快来快来数一数、二四六七八」と歌いながら走っていた。そしてレジ係は数えたコインを不機嫌そうに戻してまた数えました...
こんにちは、キキはとても素敵な女の子で、別の方法で数を数えるのが大好きです。たとえば、X 枚のコインを数えるとき、N 回数えます。毎回、彼女はコインをいくつかの同じサイズのグループに分け、グループのサイズ Mi と残りのコインの数 Ai をメモに書き留めます。
ある日、キキの父親がキキのメモを見つけて、キキが数えているコインの枚数を知りたがりました。
最初の行は T で、テスト ケースの数を示します。
各ケースには、1 行目に N、2 行目に Mi(1
入力と出力の数値はすべて整数です。
1
それぞれのケースについて、サンプル出力形式で Kiki が数えていた最小の正の整数 X を出力します。解決策がない場合は、-1 を出力します。
2
2
14 57
5 56
5
19 54 40 24 80
11 2 36 20 76
サンプル出力
ケース 1: 341
ケース 2: 5996
質問の意味: お金を数えるさまざまな方法を教えて、要件を満たす最低金額を見つけてください。
アイデア: 一見すると中国剰余定理に関する問題のように見えますが、この問題の法は必ずしもペアごとの逆素数ではありません。したがって、これは拡張ユークリッド アルゴリズムを理解する必要があるモジュラー線形方程式を解くことによって実行できます。そのアイデアは、2 つを継続的にマージして取得することです。まず 2 つの合同方程式を見つけ、一般解を N、N=r1(mod(m1))、N=r2(mod(m2)) とします。これは明らかに k1*m1+r1=k2*m2 に変換できます。 +r2 ;--->k1*m1+(-k2*m2)=r2-r1; a=m1,b=m2,x=k1,y=(-k2),c=r2-r1 という式が成り立つと仮定します。 ax +by=c と書きます。拡張ユークリッドで x を解き、x を元の方程式の最小の正の整数解 (x*(c/d)%(b/d)+(b/d) に変換します。 %(b/d); この場合、この x は元の方程式の最小の整数解になります。したがって、N=a*(x+n*(b/d))+r1====N=(a*b/d)*n+(a*x+r1)、ここで n だけが未知の数であるため、これは別の式 N=(a*x+r1)(mod(a*b/d)) であり、2 つの式を 1 つの式に変換し続ける限り、最終的にこの解を解くことができます。方程式系
ACコード:
[CP]
#include
名前空間 std を使用します。
int M[N],A[N];
int Gcd(int a,int b)
{return b==0?a:Gcd(b,a%b);}
void gcd(int a,int b,int &d,int &x,int &y)
{
If(!b) x=1、y=0、d=a;
else gcd(b,a%b,d,y,x),y-=a/b*x;
}
int main()
{
整数
Scanf("%d",&T);
for(int k=1;k
{
整数
scanf("%d",&n);
for(int i=0;i!=n;++i) scanf("%d",&M[i]);
for(int i=0;i!=n;++i) scanf("%d",&A[i]);
int x,y,d
int a=M[0],c1=A[0];
bool flag=false
for(int i=1;i
int r=b/d;
x=(c/d*x%r+r)%r;
c1=a*x+c1;
a=a*r;
}
If(フラグ) printf("ケース %d: -1n",k);
それ以外
int ans=1;
If(c1==0)//すべての剰余が 0 の特殊なケース
for(int i=0;i!=n;++i)
ans=M[i]/Gcd(ans,M[i])*ans;
printf("ケース %d: %dn",k,ans);
else printf("Case %d: %dn",k,c1);
}
} 0 を返します。
}
作者: smallacmer