[Educatinal Codeforces Round 173(Div.2)] - B. Digits

https://codeforces.com/contest/2043/problem/B

Educational Codeforces Round 173(Div.2) - B. Digits

문제 유형: 수학, 정수론

시간 제한: 1초

메모리 제한: 256MB

 

문제

Artem wrote the digit d on the board exactly n! times in a row. So, he got the number dddddd…ddd (exactly n!

digits).

Now he is curious about which odd digits from 1to 9 divide the number written on the board.

 

Artem은 정수 d를 정확히 n!번 연속으로 썼다. ddddd.....dddd가 n!자릿수만큼 있다.

그는 1~9까지의 어떤 홀수가 이 수를 나누는지 궁금해졌다.

 

입력

The first line contains a single integer t (1≤t≤100) — the number of test cases. The next t test cases follow.

Each test case consists of a single line containing two integers n and d (2≤n≤10^9, 1≤d≤9).

 

첫째 줄에 테스트케이스의 수인 정수 t가 주어진다. 

각 테스트 케이스는 n과 d가 입력된다.

 

출력

For each test case, output the odd digits in ascending order that divide the number written on the board.

 

각 테스트 케이스 별로, 오름차순으로 약수가 되는 홀수들을 각 줄에 출력해라.

 

풀이

Editorial: https://codeforces.com/blog/entry/137801

두 가지 풀이가 있다.

우선 공통적으로, 1은 모든 수의 약수이다.

그리고, d=5인 경우에만 5의 배수임이 충족된다.

 

1. 순수 수학적 스킬

 3: 모든 자릿수의 합이 3의 배수이면 되는데, n >= 3인 경우, 이거나 d가 3의 배수인 경우 반드시 조건을 충족한다.

 n>= 3인 경우 충족되는 이유는, 3! = 6이므로, 3의 배수이고, 즉 모든 자릿수의 합은 d * (3의배수)이므로 조건이 충족된다.

 7: 자릿수를 세 자리씩 끊어서 각각 +, -를 씌우고 더한 값이 7의 배수이면 그 수는 7의 배수가 된다.

 예를 들어, 1234569에서 1 - 234 + 569는 7의 배수이므로 1234569는 7의 배수가 된다.

 트릭이 하나 있다. n >=3인경우, 3!=6이고, n!(n>3)인경우는 반드시 6의 배수임을 알 수 있는데, 3자리수씩 분할한 두 쌍의 합이 항상 0   임을 알 수 있다. 즉, +(ddd -ddd)의 꼴로 묶일 수 있다. 모두 더하면 0이 되므로 7의 배수이다.

  9: n >= 6인 경우, 3을 최소 두 번 곱하게 된다. 모든 자릿수의 합 d * n!에서 n>=6이면, 반드시 9의 배수가 된다는 뜻이다.

     n < 6인 경우, 충분히 작으므로 직접 구할 수 있다. 

 

2. n!을 줄여보기

  숫자 d를 n!번 반복한 숫자는 항상 (n-1)!번 반복한 숫자로 나누어떨어진다.

  424242는 42로 나누어떨어진다.

  즉, n이 커지더라도 m까지만 보아도 결과를 알 수 있다. (n > m)

 

  7!자리의 숫자는 항상 1,3,7,9의 배수 성질을 만족한다.

  n >= 7부터는 모두 같은 결과를 가진다.

  7!자리수 정도는 충분히 계산해볼만 하다. 3, 9의 경우는 간단하므로 넘긴다.

 

  수가 작아졌을 때, 7의배수 판별은 다음과 같이 할 수 있다:

  문제에서 다루는 수의 형태는 d * (11111......111)의 형태이다.

  (1111...111) mod 7을 구하는 방법으로, 각 자릿수마다 모듈러 연산을 누적하면 된다.

  즉, temp = 0부터 시작해서, temp = (temp *10 + 1) %7을 해주면 된다.

  여기에 d를 곱한 값에 7을 나눠서 떨어진다면, 7의 배수이다.

 

 

코드

C++

 

1번 코드

#include <bits/stdc++.h>

using namespace std;

int res[] = {0, 1, 2, 6, 24, 120};
int fact(int n) {
  if (n >= 6)
    return 720;
  return res[n];
}

void solve() {
  vector<int> ans = {1};
  int n, d;
  cin >> n >> d;

  if (n >= 3 || d % 3 == 0)
    ans.push_back(3);
  if (d == 5)
    ans.push_back(5);
  if (n >= 3 || d == 7)
    ans.push_back(7);
  if (n >= 6 || (fact(n) * d) % 9 == 0)
    ans.push_back(9);

  for (const auto &num : ans) {
    cout << num << " ";
  }
  cout << "\n";
}

int main(int argc, char *argv[]) {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

 

2번 코드

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int fact[] = {0, 1, 2, 6, 24, 120, 720, 5040};

void solve() {
  int n, d;
  cin >> n >> d;
  n = min(n, 7);

  int nf = fact[n];
  vector<int> ans = {1};

  int sum_digits = d * nf;
  if (sum_digits % 3 == 0)
    ans.push_back(3);

  if (d == 5)
    ans.push_back(5);

  ll temp = 0;
  for (int i = 0; i < nf; ++i) {
    temp = (temp * 10 + 1) % 7;
  }
  if ((temp * d) % 7 == 0)
    ans.push_back(7);

  if (sum_digits % 9 == 0)
    ans.push_back(9);

  for (const auto &i : ans) {
    cout << i << " ";
  }
  cout << "\n";
}

int main(int argc, char *argv[]) {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}