Code Chef DSA学习系列:3的倍数

Question

考虑一个非常长的K位数N，其中包含数字d0、d1、...、dK-1 (以十进制记法表示；d0是最高有效位，dK-1是最低有效位)。这个数字太大了，我们不能在输入时显式地给出它；相反，你只能给出它的起始数字和构造数字的余数的一种方法。

具体地说，你得到了d0和d1；对于每个i≥2，di是前面所有(更重要的)数字的和，模10 -更正式地说，以下公式必须成立：

​

​

确定N是否为3的倍数。

输入

输入的第一行包含一个整数T，表示测试用例的数量。测试用例的描述如下。每个测试用例的第一行也是唯一一行包含三个空格分隔的整数K、d0和d1。

输出

对于每个测试用例，如果数字N是3的倍数，则打印包含字符串"YES“(不带引号)或"NO”(不带引号)的一行。

约束条件1≤T≤1000

2≤K≤1012

1≤d0≤9

0≤d1≤9

示例

输入：

3.

5 3 4

13 8 1

760399384224 5 1

输出：

不是

是

是

解释

示例情况1:整数N是34748，不能被3整除，所以答案是否定的。

示例2:整数N是8198624862486，可以被3整除，所以答案是肯定的。

问题已结束

在this问题中，在给定的示例测试用例中，我们有k=760399384224、d0=5和d1=1。现在我们知道，如果一个数字的位数之和是3的倍数，那么它就是3的倍数。因此，在这里应用它，我们将数字n分成3部分。

第1部分:前3位-> 516，(5+1+6) mod 3 ==0，因此rem1 = 0。

第二部分:接下来是(2486)的(k-3)/4次重复，或者，rem2 = ((2+4+8+6)*((k-3)/4))%3= 1

第3部分:最后(k-3)%4 =1位数字将是2(来自2486重复)，因此rem3 = 2%3=2

所以最终的答案应该是(rem1+rem2+rem3)%3

我为这个逻辑写了下面的代码：

#include<iostream>
#define ll long long
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
         ll k;
         cin>>k;
         int d0,d1;
         cin>>d0>>d1;
         int d2 = (d0+d1)%10;
         int d[4];
         d[0] = (d0+d1+d2)%10;
         d[1] = (2*d[0])%10;
         d[2] = (2*d[1])%10;
         d[3] = (2*d[2])%10;
         ll rem1 = (d0+d1+d2)%3,rem2,rem3=0;
         rem2 = (20*(((k-3)/4)%3))%3;
         ll x = (k-3)%4;
         if(x!=0)
         {
            for(int i=0; i<x; ++i)
            rem3+=d[i];
            rem3 = rem3%3;
         }
         else
             rem3 =0;
         if(k==2)
         {
             rem1 = (d0+d1)%3;
             rem2=0;
             rem3=0;
         }
         if((rem1+rem2+rem3)%3==0)
            cout<<"YES"<<endl;
         else
            cout<<"NO"<<endl;
    }
}

现在他们在他们的测试用例中给了我WA。我想不出一个可能的测试用例不能与此代码一起工作。所以请谁帮帮我。

Answer 1

这里有一个明显的不匹配。您可能可以使用以下JavaScript代码来查找更多信息：

​

function f(k, d0, d1){
  let d2 = (d0+d1)%10;
  let d = new Array(4).fill(0);
  d[0] = (d0+d1+d2)%10;
  d[1] = (2*d[0])%10;
  d[2] = (2*d[1])%10;
  d[3] = (2*d[2])%10;
  let rem1 = (d0+d1+d2)%3, rem2, rem3=0;
  rem2 = (20*((~~((k-3)/4))%3))%3;
  let x = (k-3)%4;
  if(x!=0)
  {
    for(let i=0; i<x; ++i)
    rem3+=d[i];
    rem3 = rem3%3;
  }
  else
      rem3 =0;
  if(k==2)
  {
      rem1 = (d0+d1)%3;
      rem2=0;
      rem3=0;
  }
  if((rem1+rem2+rem3)%3==0)
    return true

  return false
}

function bruteForce(k, d0, d1){
  let d = (d0 + d1) % 10;
  let n = 10 * d0 + d1;
  for (let i=3; i<=k; i++){
    n = 10 * n + d;
    d = (2 * d) % 10;
  }
  return [n % 3 == 0, n];
}

let str = "";

str += "Examples:\n";
str += "(5, 3, 4)\n" + bruteForce(5, 3, 4) + "\n\n";
str += "(13, 8, 1)\n" + bruteForce(13, 8, 1) + "\n\n"

var k = 7;
var mismatch = false;

for (let i=1; i<10; i++){
  for (let j=0; j<10; j++){
    const _f = f(k, i, j);
    const _bruteForce = bruteForce(k, i, j);

    if (_bruteForce[0] != _f){
      str += "Mismatch:\n" + 
        `(${ k }, ${ i }, ${ j })\n` +
        "f: " + _f +
        "\nbruteForce: " + _bruteForce + "\n\n";
      mismatch = true;
    }
    if (mismatch)
      break;
  }
  if (mismatch)
    break;
}

console.log(str);

​

Answer 2

#include <stdio.h>

void isMulti3(long long int K, long long int d0, long long int d1) {
    long long int mod1 = (d0 + d1) % 10;

    long long int sum_mod1 = d0 + d1 + mod1;
    
    long long int rep = (K-3)/4;
    long long int mod2[4];
    mod2[0] = (2*mod1) % 10;
    mod2[1] = (4*mod1) % 10;
    mod2[2] = (8*mod1) % 10;
    mod2[3] = (6*mod1) % 10;

    long long int sum_mod2 = 0;
    for(int i = 0; i < 4; i++) {
        sum_mod2 += mod2[i];
    }

    long long int unrep = (K - 3) % 4;
    long long int sum_mod3 = 0;
    for(int i = 0; i < unrep; i++) sum_mod3 += mod2[i]; 
    long long int isMod1 = sum_mod1 % 3;
    long long int isMod2 = ((rep%3)*(sum_mod2%3)) % 3;
    long long int isMod3 = sum_mod3 % 3;

    if((isMod1 + (isMod2 + isMod3)%3)% 3 == 0) printf("YES\n");
    else printf("NO\n");

}
int main() {
    int T;
    scanf("%d", &T);

    for(int i = 0; i < T; i++) {
        long long int K;
        long long int d0, d1;
        scanf("%lld %lld %lld", &K, &d0, &d1);
        if(K == 2) {
            if((d0 + d1) % 3 == 0) printf("YES\n");
            else printf("NO\n");
        }
        else isMulti3(K, d0, d1);


    }
}

我想你就是在codechef讨论门户上问这个问题的那个人。我在那里回答了这个问题，我正在分享这个链接。https://discuss.codechef.com/t/dsa-learning-series-multiple-of-3/77174/4?u=nazishkaunain所以你错了的地方是：

你可以使用这样的事实：(a+b+c)mod3 != amod3+bmod3+cmod3；但是(a +b+ c) mod3=(amod3+(bmod3+cmod3)mod3)mod3)mod3；只有当n mod3= 0 => (a +b+ c) mod3=0时，n(n=a+b+ c)才能被3整除。