6

与えられた数が7で割り切れるかどうかを確認する必要があります。これは通常、のようなことを行うだけで実行されn % 7 == 0ますが、問題は、与えられた数が最大100000000になる可能性があり、これはに収まらないことlong longです。

もう1つの制約は、使用可能なメモリが数キロバイトしかないため、配列を使用できないことです。

1数値はstdinにあり、出力は/になると予想しています0。

これは例です

34123461273648125348912534981264376128345812354821354127346821354982135418235489162345891724592183459321864592158
0

約7つの整数変数とを使用して実行できるはずですcin.get()。また、標準ライブラリのみを使用して実行する必要があります。

4

9 に答える 9

26

7 による除算に関する既知のルールを使用できます。つまり、右から 3 桁ごとにグループ化し、それらを交互に減算および加算し始めると、結果の 7 による割り算は元の数値と同じになります。

元。：

testing 341234612736481253489125349812643761283458123548213541273468213
        549821354182354891623458917245921834593218645921580

   (580-921+645-218+593-834+921-245+917-458+623-891+354-182
    +354-821+549-213+468-273+541-213+548-123+458-283+761-643
    +812-349+125-489+253-481+736-612+234-341 
    = 1882 )
    % 7 != 0 --> NOK!

このルールには他の代替手段があり、すべて簡単に実装できます。

于 2009-10-11T14:23:47.970 に答える
19

紙の上で除算を行う方法を考えてください。最初の1桁か2桁を見て、7の最も近い倍数を書き留め、余りを引き下げます。整数をメモリにロードする必要がないため、任意の長さの数値でこれを行うことができます。

于 2009-10-11T14:13:09.380 に答える
13

7 による割り切れるルールのほとんどは数字レベルで機能するため、文字列に問題なく適用できます。

于 2009-10-11T14:14:21.513 に答える
3

7 を法とする数値の値を計算できます。

つまり、これまでの各桁 d と値 n について、n = (10 * n + d) % 7 を計算します。

これには、除数 7 または基数 10 とは独立して機能するという利点があります。

于 2009-10-11T18:41:12.787 に答える
2

7 を法とする数値の値を計算できます。

つまり、これまでの各桁 d と値 n について、n = (10 * n + d) % 7 を計算します。

これには、除数 7 または基数 10 とは独立して機能するという利点があります。

あるプログラミング コンテストで、この問題をまったく同じ方法で解決しました。必要なコードの断片は次のとおりです。

int sum = 0;
while (true) {
  char ch;
  cin>>ch;
  if (ch<'0' || ch>'9') break; // Reached the end of stdin
  sum = sum*10; // The previous sum we had must be multiplied
  sum += (int) ch;
  sum -= (int) '0'; // Remove the code to get the value of the digit
  sum %= 7; 
}

if (sum==0) cout<<"1";
else cout<<"0";

このコードは、剰余算術の単純なルールのおかげで機能しています。7だけでなく、実際にはどの除数でも機能します。

于 2010-09-21T07:37:22.533 に答える
1

7 で割り切れる大きな数を引くことから始めます。

7 で割り切れる数の例には、700、7000、70000、140000000、42000000000 などがあります。

あなたが与えた特定の例では、280000000000（いくつかのゼロ）0000を引いてみてください。

さらに簡単に実装するには、70000000000 (いくつかのゼロ) 0000 のように可能な最大数を繰り返し減算します。

于 2009-10-11T14:15:05.100 に答える
0

N = abc

3桁の数字が7の倍数であるかどうかを確認する簡単なアルゴリズムがあります。

aをxに置き換えて、それをbcに追加します。xは、7の倍数である2桁の数の10であり、数百はaです。

N = 154; x = 2; 2 + 54 = 56; 7|56および7|154

N = 931; x = 4; 4 + 31 = 35; 7|35および7|931

N = 665; x = 5; 5 + 65 = 70; 7|70および7|665

N = 341; x = 6; 6 + 41 = 47; 7ł47と7ł341

Nがさまざまな期間によって形成される場合、ある期間の結果の逆加算を次の期間の合計に追加する必要があります。次のようになります。

N = 341.234

6 + 41 = 47; --41mod7≡1; 1 + 4 + 34 = 39; 7ł39と7łN

N = 341.234.612.736.481

341.234の結果は39です。この結果から続けると、次のようになります。

-39mod7≡3; 3 + 5 + 6 + 1 + 2 + 1 = 18; -18mod7≡3; 3 + 0 + 36 = 39; -39mod7≡3; 3 + 1 + 81 = 85; 7ł85と7łN

このルールは暗算によって完全に適用される可能性があり、非常に迅速です。これは、2.005で作成した別のルールから派生したものです。これは、任意の大きさの数と13による除算に対して機能します。

于 2012-12-23T21:54:00.420 に答える
0

私は最近、数値を分割する作業を行ったので、特定の数値を取得することを示唆します-これは、他の回答のいくつかで必要になるものです-整数除算とモジュラスを使用して数字を取得することを考えてください。

より小さい数、たとえば がある場合123、どのようにして1、2、およびを取得し3ますか? 特にベース10で作業しているので...

于 2009-10-11T14:29:48.850 に答える
-1

最初に文字列の大きな数を取り、次に文字列のすべての桁を合計します。最後に if(sum%7==0) をチェック

コード： 

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,i,j,sum,k;
    sum=0;
    string s;
    cin>>s;
    for(i=0;i<s.length();i++)
    {
        sum=sum+(s[i]-'0');
    }

    if(sum%7==0)
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }

    return 0;
}
于 2016-04-23T11:23:02.060 に答える