[Codeforces] number theory (R1200) Part.8

[Codeforces] number theory (R1200) Part.8

题单:https://codeforces.com/problemset/page/6?tags=number%20theory,0-1200

1511B. GCD Length

原题指路:https://codeforces.com/problemset/problem/1511/B

题意 ($2\mathrm{s}$)

给定三个整数$a,b,c$,构造任两个正整数$x,ys.t.x$的十进制表示(不含前导零,下同)包含$a$个数码,$y$的十进制表示包含$b$个数码,$\gcd (x,y)$的十进制表示包含$c$个数码.

有$t(1\le t\le 285)$组测试数据.每组测试数据输入三个整数 a , b , c    ( 1 ≤ a , b ≤ 9 , 1 ≤ c ≤ min ⁡ { a , b } ) a,b,c\ \ (1\leq a,b\leq 9,1\leq c\leq \min\{a,b\}) a,b,c  (1≤a,b≤9,1≤c≤min{a,b}).数据保证有解.

思路

令$x=1\underset{(a-c)个}{\underbrace{0\cdots 0}}\underset{(c-1)个}{\underbrace{0\cdots 0}},y=1\underset{(b-c)个}{\underbrace{1\cdots 1}}\underset{(c-1)个}{\underbrace{0\cdots 0}}$.因$\gcd (10\cdots 0,11\cdots 1)=1$,故满足条件.

代码

void solve() {
	int a, b, c; cin >> a >> b >> c;
    cout << "1" << string(a - 1, '0') << ' ' << string(b - c + 1, '1') << string(c - 1, '0') << endl;
} 

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9

---

---

1514A. Perfectly Imperfect Array

原题指路:https://codeforces.com/problemset/problem/1514/A

题意

称一个序列是好的,如果它存在一个非空的子列使得其中元素之积不是完全平方数.

有$t(1\le t\le 100)$组测试数据.每组测试数据第一行输入一个整数$n(1\le n\le 100)$,表示序列长度.第二行输入$n$个整数$a_1,\cdots ,a_n(1\le a_i\le 1\mathrm{e}4)$.

对每组测试数据,若序列$a[]$是好的,输出"YES";否则输出"NO".

思路

注意到若序列$a[]$中包含一个非完全平方数,则它是好的.

代码

bool check(int x) {
    int tmp = sqrt(x);
    return x == tmp * tmp;
}

void solve() {
	int n; cin >> n;

    bool ok = false;
    while (n--) {
        int x; cin >> x;
        ok |= !check(x);
    }
    cout << (ok ? "YES" : "NO") << endl;
} 

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

---

1515B. Phoenix and Puzzle

原题指路:https://codeforces.com/problemset/problem/1515/B

题意 ($2\mathrm{s}$)

有$n$个如图(1)所示的等腰直角三角形的拼图,问能否用它们拼成一个正方形,使得所有的拼图都用完,若能则输出"YES";否则输出"NO".

有$t(1\le t\le 1\mathrm{e}4)$组测试数据.每组测试数据输入一个整数$n(1\le n\le 1\mathrm{e}9)$.

思路

如图(2)和图(3)所示,可用$2$块或$4$块拼图拼成一个小正方形.设小正方形的数量为$x$,则用小正方先能拼成一个大正方形的充要条件是:$x$是完全平方数.

有解的条件只能是下列两条件之一:①$n$是$2$的倍数,且$\frac{n}{2}$是完全平方数;②$n$是$4$的倍数,且$\frac{n}{4}$是完全平方数.

[证] 下面证明无其他解.设直角三角形的直角边长为$1$,则斜边长为$\sqrt{2}$.

设拼成的大正方形的边长用到了$a$条直角边和$b$条斜边,则其边长为$a+\sqrt{2}b$.

注意到大正方形的面积${\left(a+\sqrt{2}b\right)}^2$是有理数,则$a=0$或$b=0$.

代码

bool check(int x) {
    int tmp = sqrt(x);
    return x == tmp * tmp;
}

void solve() {
	int n; cin >> n;

    bool ok = false;
    ok |= n % 2 == 0 && check(n / 2);
    ok |= n % 4 == 0 && check(n / 4);
    cout << (ok ? "YES" : "NO") << endl;
} 

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

---

1520B. Ordinary Numbers

原题指路:https://codeforces.com/problemset/problem/1520/B

题意 ($2\mathrm{s}$)

称一个整数是好的,如果它的所有数码都相同.

有$t(1\le t\le 1\mathrm{e}4)$组测试数据.每组测试数据输入一个整数$n(1\le n\le 1\mathrm{e}9)$,问$[1,n]$中好的数的个数.

思路

注意到好的数可表示为$d(10^0+10^1+\cdots +10^k)$,则只需统计$s.t.d(10^0+10^1+\cdots +10^k)\le n$的整数对$(d,k)$的个数,其中$d\in [1,9],k\in [0,8]$,暴力统计即可.

代码

void solve() {
	int n; cin >> n;
    
    int ans = 0;
    for (ll pow10 = 1; pow10 <= n; pow10 = pow10 * 10 + 1) {
        for (int d = 1; d <= 9; d++) 
            ans += pow10 * d <= n;
    }
    cout << ans << endl;
}

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

---

1521A. Nastia and Nearly Good Numbers

原题指路:https://codeforces.com/problemset/problem/1521/A

题意

给定两整数$A,B$,①称一个整数是好的,如果它能被$AB$整除;②称一个整数是近似好的,如果它能被$A$整除.构造三个相异的正整数$x,y,z$,使得其中恰有一个好的数、恰有两个近似好的数,且$x+y=z$.

有$t(1\le t\le 1\mathrm{e}4)$组测试数据.每组测试数据输入两个整数$A,B(1\le A,B\le 1\mathrm{e}6)$.

对每组测试数据,若有解,输出"YES"并输出满足条件的三个整数$x,y,z(1\le x,y,z\le 1\mathrm{e}18)$;否则输出"NO".

思路

①$B=1$时,被$AB$整除即被$A$整除,此时好的和近似好的等价,无解.

②$B\ge 2$时,取$A+AB=A(B+1)$.

代码

void solve() {
	int a, b; cin >> a >> b;

    if (b == 1) cout << "NO" << endl;
    else {
        cout << "YES" << endl;
        cout << a << ' ' << (ll)a * b <<' ' << (ll)a * (b + 1) << endl;
    }
}

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

---

1525A. Potion-making

原题指路:https://codeforces.com/problemset/problem/1525/A

题意

有A和B两种水,现要配置包含$k\%$的A水和$(100-k)\%$的B水的水,每次操作可加$1$单位的A水或B水,问最少操作次数.

有$t(1\le t\le 100)$组测试数据.每组测试数据输入一个整数$k(1\le k\le 100)$.

思路

首先必有解,最坏可加$k$次A水和$(100-k)$次B水.

设A水、B水分别加$x$、$y$次,则$\frac{x}{x+y}=\frac{k}{100}$.显然$(x+y)\mid 100$,不妨设$z(x+y)=100$,则$zx=k$,即$x=\frac{k}{z}$.

代入$z(x+y)=100$,解得$y=\frac{100-k}{z}$,则$ans=x+y=\frac{100}{z}$.

因$x,ans\in \mathbb{Z}$,则$z\mid k,z\mid 100$.为使得$ans$最小,取$z=\gcd (100,k)$.

代码

void solve() {
	int k; cin >> k;
    cout << 100 / gcd(100, k) << endl;
}

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9

---

---

1535B. Array Reodering

原题指路:https://codeforces.com/problemset/problem/1535/B

题意

对序列$a_1,\cdots ,a_n$称一对下标$(i,j)(1\le i<j\le n)$是好的,如果$\gcd (a_i,2a_j)>1$.将$a[]$排序,使得其好的下标的对数最多,输出好的下标的对数.

有$t(1\le t\le 1000)$组测试数据.每组测试数据第一行输入一个整数$n(2\le n\le 2000)$.第二行输入$n$个整数$a_1,\cdots ,a_n(1\le a_i\le 1\mathrm{e}5)$.数据保证所有测试数据的$n$之和不超过$2000$.

思路

显然应将偶数排在前面,奇数排在后面.显然偶数间顺序无关.对奇数$a_i,a_j,\gcd (a_i,2a_j)=\gcd (a_i,a_j)$,故奇数间的顺序无关.

代码

void solve() {
	int n; cin >> n;
	vi a(n);
	for (int& ai : a) cin >> ai;

	sort(all(a), [&](const int& A, const int& B) {
		return A % 2 < B % 2;
		});

	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++)
			ans += gcd(a[i], a[j] * 2) > 1;
	}
	cout << ans << endl;
}

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

---

1541B. Pleasant Pairs

原题指路:https://codeforces.com/problemset/problem/1541/B

题意

给定一个包含$n$个相异整数的序列$a_1,\cdots ,a_n$,求使得$1\le i<j\le n$且$a_i\cdot a_j=i+j$的整数对$(i,j)$的对数.

有$t(1\le t\le 1\mathrm{e}4)$组测试数据.每组测试数据第一行输入一个整数$n(2\le n\le 1\mathrm{e}5)$.第二行输入$n$个相异的整数$a_1,\cdots ,a_n(1\le a_i\le 2n)$.数据保证所有测试数据的$n$之和不超过$2\mathrm{e}5$.

思路

注意到$a_i\cdot a_j=i+j\le 2n$,可枚举每个$(i+j)$的值后再枚举每个$a_i$,检查是否存在满足条件的元素即可.

满足上述条件的整数对$(i,j)$有$O(n\log n)$对.

[证] 设$a_i=x$,则$a_j$至多有$\frac{2n}{x}$种取值.$\sum _{i=1}^n\frac{2n}{i}=2n\sum _{i=1}^n\frac{1}{i}=O(n\log n)$.

代码

void solve() {
	int n; cin >> n;
  umap pos;  // 每个a_i的值所在的下标
  for (int i = 1; i <= n; i++) {
    int a; cin >> a;
    pos[a] = i;
  }

  int ans = 0;
  for (int i = 2; i <= 2 * n; i++) {  // 枚举i+j
    for (int j = 1; j * j < i; j++) {  // 枚举a[i],注意不是<=
      if (i % j ==  0) {
        int k = i / j;
        if (pos[j] && pos[k] && pos[j] + pos[k] == i) ans++;
      }
    }
  }
  cout << ans << endl;
} 

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

---

1543A. Exciting Bets

原题指路:https://codeforces.com/problemset/problem/1543/A

题意

给定两正整数$a,b$.现有两种操作:①$a++,b++$;②$a--,b--$,此操作当且仅当$a,b>0$时可执行.问经过若干次(可能为零次)操作后$\gcd (a,b)$的最大值.

有$t(1\le t\le 5000)$组测试数据.每组测试数据输入两个整数$a,b(0\le a,b\le 1\mathrm{e}18)$.

对每组测试数据,若$\gcd (a,b)$可达到无穷大,则输出"0 0";否则先输出$\gcd (a,b)$的最大值,再输出达到最大值所需的最小步数.

思路

①$a=b$时,一直做操作①即可使得$\gcd (a,b)=INF$.

②不妨设$a\ge b$.$\gcd (a,b)$能取得的最大值是$a-b$.

​ [证] 注意到$\gcd (a,b)=\gcd (a-b,b)$,其中$g=a-b$在操作过程中不变,

​ 为使得$\gcd (a,b)$最大,应通过操作将$b$变为$g$的倍数.

​ $\le b$的最大的$g$的倍数是$\lfloor \frac{b}{g}\rfloor \cdot g$,则将$b$减至该倍数所需步数为$b-\lfloor \frac{b}{g}\rfloor \cdot g=b\%g$.

​ 显然将$b$加至$\ge b$的最小的$g$的倍数所需步数为$g-b\%g$.

代码

void solve() {
	ll a, b; cin >> a >> b;
    
  if (a == b) cout << "0 0" << endl;
  else {
    if (b > a) swap(a, b);

    ll g = a - b;
    cout << g << ' ' << min(b % g, g - b % g) << endl;
  }
} 

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

---

1549A. Gregor and Cryptography

原题指路:https://codeforces.com/problemset/problem/1549/A

题意

给定一个素数$p$,求两个整数$a,bs.t.2\le a<b\le p,p\%a=p\%b$.

有$t(1\le t\le 1000)$组测试数据.每组测试数据输入一个素数$p(5\le p\le 1\mathrm{e}9)$.

思路

因素数$p\ge 5$,则$p$是奇数,进而$(p-1)$是偶数.取$a=2,b=p-1$即可.

代码

void solve() {
	int n; cin >> n;
  cout << 2 << ' ' << n - 1 << endl;
}

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9

---

---