6

我必须检查，如果给定的数字可以被 7 整除，这通常只是通过做类似的事情来完成n % 7 == 0，但问题是，给定的数字最多可以有 100000000，这甚至不适合long long.

另一个限制是，我只有几千字节的可用内存，所以我不能使用数组。

我希望数字在标准输入上，输出为1/ 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

想想你如何在纸上进行除法。你看第一个或两个数字，写下最接近的七的倍数，把余数拿下来，依此类推。您可以对任意长度的数字执行此操作，因为您不必将整个数字加载到内存中。

于 2009-10-11T14:13:09.380 回答
13

大多数可被七规则整除的规则都在数字级别上起作用，因此将它们应用于字符串应该没有问题。

于 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

因为我最近确实处理了分解数字的工作，所以我会暗示要获得特定的数字——这是你在其他一些答案中所需要的——考虑整数除法并使用模数从中取出数字。

如果你有一个更小的数字，比如123，你将如何从中得到1、2和3？特别是因为你在base 10工作......

于 2009-10-11T14:29:48.850 回答
0

N = abc

有一个简单的算法可以验证三位数字是否是 7 的倍数：

将 a 替换为 x 并将其添加到 bc，即 x 是 7 的两位数的倍数的十位，其百位是 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；- 41 模 7 ≡ 1；1 + 4 + 34 = 39；7?39 和 7?N

N = 341.234.612.736.481

341.234 的结果是 39。从这个结果继续我们有：

-39 模 7 ≡ 3；3 + 5 + 6 + 1 + 2 + 1 = 18；- 18 mod 7 ≡ 3; 3 + 0 + 36 = 39；- 39 mod 7 ≡ 3; 3 + 1 + 81 = 85；7?85 和 7?N

这个规则可以完全通过心算来应用，而且速度非常快。它源自我在 2.005 中创建的另一条规则。它适用于任何数量级的数字和可被 13 整除。

于 2012-12-23T21:54:00.420 回答
-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 回答