สำหรับโจทย์ข้อนี้ต้องการให้หารเศษจากการหารเลขด้วย $3$ และ $11$

30% ของชุดทดสอบ : $N<1\ 000\ 000\ 000$

เนื่องจากในชุดทดสอบนี้ค่าของ $N$ อยู่ในช่วงไม่เกิน integer จึงสามารถหาค่าได้โดยการใช้ arithmetic operator ปกติ

Code

#include<bits/stdc++.h>

using namespace std;

int n;

int main() {
	scanf("%d", &n);
	printf("%d %d", n % 3, n % 11);
}

100% ของชุดทดสอบ : $N<10^{1\ 000\ 000}$

ในชุดทดสอบนี้เลขดังกล่าวมีค่ามากถึง $10^{1\ 000\ 000}$ หรือ 1 ล้านหลัก

ให้ $x$ เป็นตัวเลข 1 ล้านหลัก โดย $x = \overline{a_1a_2\dots a_k}$ และ $k$ เป็นจำนวนหลักของ $x$ ซึ่ง $x$ สามารถเขียนได้อยู่ในรูปของ $10^{k-1}\cdot a_1+10^{k-2}\cdot a_2+\dots+10^0\cdot a_k = \sum\limits_{i=1}^{k} 10^{k-i}\cdot a_i$

จากคุณสมบัติที่ว่า $(a+b)$ $\text{mod}$ $m=a$ $\text{mod}$ $m+b$ $\text{mod}$ $m$ และ $(a\cdot b)$ $\text{mod}$ $m=a$ $\text{mod}$ $m\cdot b$ $\text{mod}$ $m$

จึงได้ว่า $\sum\limits_{i=1}^{k} 10^{k-i}\cdot a_i$ $\text{mod}$ $m=\sum\limits_{i=1}^{k} (10^{k-i}\cdot a_i$ $\text{mod}$ $m)$

Time Complexity : $O(K)$ หรือ $O(\log_{10}{N})$

Code

#include<bits/stdc++.h>

using namespace std;

int a, b;
string s;

int main() {
	cin >> s;
	for (auto &e: s) {
		a = (a * 10) + (e - '0'), a %= 3;
		b = (b * 10) + (e - '0'), b %= 11;
	}
	printf("%d %d", a, b);
}