概述
A - Mathematically Hard——欧拉函数的简单应用
题意
求1~n的欧拉函数的平方的和。
思路
打表求出5e6内的欧拉函数，然后再求平方的前缀和。
需要注意的两点：
1.要用unsigned long long ，只用long long的话范围不够。
2.注意内存，开两个数组似乎就会爆空间。
先用了线性筛法，一直疯狂爆内存，换了埃式筛法，就过了 …我好南啊。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll unsigned long long
using namespace std;
const int N = 5e6 + 10;
ll phi[N] = {0};
int cas,a,b;
void euler1(int n) {
for(int i = 2; i < n; i++) phi[i] = i;
for(int i = 2; i < n; i++) {
if(phi[i] == i) {
for(int j = i; j < n; j += i) {
phi[j] = phi[j] / i * (i - 1);
}
}
}
for(int i = 2 ; i < n; i++){
phi[i] = (ll)(phi[i-1] + phi[i] * phi[i]);
}
}
int main(){
euler1(N-5);
scanf("%d",&cas);
int cnt = 0;
while(cas--){
scanf("%d %d",&a,&b);
printf("Case %d: %llun",++cnt,phi[b] - phi[a-1]);
}
return 0;
}
B - Ifter Party——分解因子
题意
有C个人，然后给他们P个食物，每个人吃Q个，然后剩下L个，给定P和L，Q > L求Q可能的情况。
思路
本题就是分解Q-L的因子，升序输出其中大于L的因子，分解因子的时候要特别注意到因子刚好是开方的情况。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
const int N = 2e5;
int cas;
ll p, l;
ll ans[N], cnt = 0;
void divide(int n) {
for(int i = 1; i <= sqrt(n); i++) {
if(n % i == 0) {
if(i > l)
ans[cnt++] = i;
if(n / i > l && i * i != n)
ans[cnt++] = n / i;
}
}
}
int main() {
scanf("%d", &cas);
for(int icas = 1; icas <= cas; icas++) {
cnt = 0;
scanf("%lld %lld", &p, &l);
divide(p - l);
printf("Case %d:", icas);
if(cnt == 0) {
printf(" impossiblen");
} else {
sort(ans,ans + cnt);
for(int i = 0 ; i < cnt; i++)
printf(" %lld", ans[i]);
puts("");
}
}
return 0;
}
C - Eid
题意
求给定的 n n n个数的LCM。
思路
利用唯一分解定理的一个性质：
令：
a
=
p
1
c
1
∗
p
2
c
2
∗
.
.
.
∗
p
m
c
m
a = p_1^{c_1}*p_2^{c_2}*...*p_m^{c_m}
a=p1c1∗p2c2∗...∗pmcm
b
=
p
1
d
1
∗
p
2
d
2
∗
.
.
.
∗
p
m
d
m
b = p_1^{d_1}*p_2^{d_2}*...*p_m^{d_m}
b=p1d1∗p2d2∗...∗pmdm
则 l c m ( a , b ) = p 1 m a x ( c 1 , d 1 ) ∗ p 2 m a x ( c 2 , d 2 ) ∗ . . . ∗ p m m a x ( c m , d m ) lcm(a,b) = p_1^{max(c_1,d_1)}* p_2^{max(c_2,d_2)}*...* p_m^{max(c_m,d_m)} lcm(a,b)=p1max(c1,d1)∗p2max(c2,d2)∗...∗pmmax(cm,dm)
所以直接找出每个质数因子的最高次幂，然后求所有每个质因子最高次幂的乘积即可。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<sstream>
#include<cmath>
#define ll long long
using namespace std;
const int N = 10010;
int m, cas, a,len;
int prime[N], prime_tot = 0, p[N], c[N],tot = 0,ans[N];
bool prime_tag[N],bk[N];
void get_prime() {
for(int i = 2 ; i < N; i++) prime_tag[i] = true;
for(ll i = 2; i < N; i++) {
for(int j = i * i; j < N; j += i) {
prime_tag[j] = false;
}
}
for(int i = 2; i < N; i++)
if(prime_tag[i]) prime[prime_tot++] = i;
}
void mul(int x) {
int c=0;
for(int i=0; i<len; i++) {
int k=ans[i]*x+c;
c=k/10;
ans[i]=k%10;
if(i==len-1&&c) {
//ans[len]=c;
len++;
}
}
}
void divide(int n) {
for(int i = 0 ; i < prime_tot && prime[i] <= n; i++) {
int tmp = 0;
if(n % prime[i] == 0) {
if(!bk[prime[i]]){
p[tot++] = prime[i];
bk[prime[i]] = true;
}
while(n % prime[i] == 0 && n > 1) {
tmp++;
n /= prime[i];
}
c[prime[i]] = max(c[prime[i]], tmp);
if(n == 1) break;
}
}
if(n > 1) {
p[tot++] = n;
c[n] = max(c[n], 1);
}
}
int qpow(int a, int b) {
int ret = 1;
while(b) {
if(b & 1) {
ret *= a;
}
a *= a;
b >>= 1;
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
get_prime();
int icas = 1;
cin >> cas;
//scanf("%d", &cas);
while(cas--) {
tot = 0;
memset(p, 0, sizeof(p));
memset(c, 0, sizeof(c));
memset(bk, 0, sizeof(bk));
memset(ans, 0, sizeof(ans));
cin >> m;
//scanf("%d",&m);
for(int i = 0; i < m; i++) {
cin >> a;
//scanf("%d",&a);
divide(a);
}
ans[0] = 1;
len = 1;
for(int i = 0; i < tot; i++) {
int num = qpow(p[i],c[p[i]]);
mul(num);
}
cout << "Case " << icas++ << ": " ;
for(int j = len - 1; j >= 0; j--)
cout << ans[j];
cout << "n";
}
return 0;
}
/*
3
5
1 2 3 5 7
3
2 20 10
4
5 6 30 60
*/
D - Trailing Zeroes (I) ——唯一分解定理推论求因数个数
题意
给一个数，求出除1以外的因子的个数。
思路
利用唯一分解定理的一个推论：
N
N
N的正约数个数为（
∏
prod
∏表示连乘）
(
c
1
+
1
)
∗
(
c
2
+
1
)
∗
.
.
.
∗
(
c
m
+
1
)
=
∏
i
=
1
m
(
c
i
+
1
)
(c_1+1)*(c_2+1)*...*(c_m+1)=displaystyleprod^m_{i=1} (c_i+1)
(c1+1)∗(c2+1)∗...∗(cm+1)=i=1∏m(ci+1)
求出 N N N的约数个数以后再减去1即可。
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
ll cas,n;
int prime[N],prime_tot = 0;
bool prime_tag[N] = {0};
void get_prime() {
for(int i = 2; i < N; i++) {
if(!prime_tag[i]) {
prime[prime_tot++] = i;
}
for(int j = 0 ; j < prime_tot && i * prime[j] < N; j++) {
prime_tag[i * prime[j]] = true;
if(i % prime[j] == 0)
break;
}
}
}
ll solve(ll n) {
ll res = 1;
for(int i = 0 ; i < prime_tot && prime[i] * prime[i] <= n; i++) {
if(n % prime[i] == 0) {
ll c = 0;
while(n % prime[i] == 0 && n > 1) {
c++;
n /= prime[i];
}
res = res * (c + 1);
if(n == 1)
break;
}
}
if(n > 1)
res = res * 2;
return res - 1;
}
int main() {
int icas = 1;
get_prime();
scanf("%lld",&cas);
while(cas--) {
scanf("%lld",&n);
printf("Case %d: %lldn",icas++,solve(n));
}
return 0;
}
E - Intelligent Factorial Factorization——唯一分解定理分解质因子
题意
给一个 N N N，将 N ！ N！ N！分解质因子。
思路
将数据范围内所有的数分解质因子，将质因子和幂储存再数组里，然后求一个前缀和就等于是将阶乘分解质因子。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
const int N = 110;
int p[N][N], c[N][N] = {0}, prime[N],ans[N][N] = {0};
int p_cnt = 0, prime_tot = 0;
bool prime_tag[N];
int n, cas, icas = 1;
void get_prime() {
for(int i = 1; i < N; i++) prime_tag[i] = true;
for(int i = 2; i < N; i++) {
for(ll j = i * i ; j < N; j += i)
prime_tag[j] = false;
}
for(int i = 2; i < N; i++)
if(prime_tag[i]) prime[prime_tot++] = i;
}
void divide(int m) {
p_cnt = 0;
int up = m;
for(int i = 0 ; i < prime_tot && prime[i] * prime[i] <= up; i++){
if(m % prime[i] == 0){
p[up][p_cnt++] = prime[i];
c[up][prime[i]] = 0;
while(m % prime[i] == 0 && m > 1){
c[up][prime[i]]++;
m /= prime[i];
}
if(m == 1)
break;
}
}
if(m > 1)
p[up][p_cnt++] = m,c[up][m] = 1;
}
void solve(){
for(int i = 2; i <= 100; i++){
for(int j = 0; j < prime_tot; j++){
ans[i][prime[j]] = ans[i - 1][prime[j]] + c[i][prime[j]];
}
}
}
int main() {
get_prime();
for(int i = 2; i <= 100; i++)
divide(i);
solve();
scanf("%d", &cas);
while(cas--) {
scanf("%d", &n);
printf("Case %d: %d = ",icas++,n);
int first = 1;
for(int i = 0 ; i < prime_tot; i++){
if(ans[n][prime[i]]){
if(first){
printf("%d (%d)",prime[i],ans[n][prime[i]]);
first = 0;
}else{
printf(" * %d (%d)",prime[i],ans[n][prime[i]]);
}
}
}
printf("n");
}
return 0;
}
F - Digits of Factorial ——对数性质
题意
n ! n! n! 在 m m m 进制下有几位数
思路
首先可以发现一个规律，对于一个数
K
K
K，它在
m
m
m 进制下的数位个数就是
l
o
g
m
K
log_mK
logmK。
那么我们要求的答案就是 a n s = l o g m n ! ans =log_m n! ans=logm n!。
根据对数的运算规律
a
n
s
=
l
o
g
m
n
!
=
l
o
g
m
1
+
l
o
g
m
2
+
.
.
.
+
l
o
g
m
n
ans =log_m n!=log_m1+log_m2+...+log_mn
ans=logm n!=logm1+logm2+...+logmn
a n s = l o g ( 1 ) + l o g ( 2 ) + l o g ( 3 ) + . . . + l o g ( n ) l o g m displaystyle ans = frac{log(1) + log(2)+log(3)+...+log(n)}{logm} ans=logmlog(1)+log(2)+log(3)+...+log(n)
我们可以通过预处理来求出所有的 l o g i logi logi,求出一个前缀和，在算答案的时候直接除以 l o g m logm logm就可以了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
int n,cas,base;
double log_[N];
void init() {
log_[0] = 0;
for(int i = 1; i < N; i++) {
log_[i] = log_[i - 1] + log(i);
}
}
int main() {
init();
scanf("%d",&cas);
int icas = 1;
while(cas--) {
scanf("%d %d",&n,&base);
double ans = log_[n];
if(n == 0) {
ans = 0;
} else {
ans /= log(base);
}
printf("Case %d: %lldn",icas++,(ll)(ans+1));
}
return 0;
}
G - Combinations——Lucas定理
题意
给定
n
,
m
n,m
n,m，要求组合数
C
n
m
C_n^m
Cnm。
思路
因为
n
,
m
n,m
n,m会很大，那么
C
n
m
C_n^m
Cnm，也会很大，同时因为存在取模 所以想到Lucas定理。
Lucas定理：
若
p
p
p是质数，则对于任意整数
1
≤
m
≤
n
1 leq mleq n
1≤m≤n，有：
C
n
m
=
C
n
m
o
d
p
m
m
o
d
p
×
C
n
/
p
m
/
p
(
m
o
d
p
)
C_n^m = C_{n mod p}^{m mod p}times C_{n/p}^{m/p}(mod p)
Cnm=Cn mod pm mod p×Cn/pm/p(mod p)
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
const int mod = 1000003;
int cas,n,k;
ll f[N];
//提前求出阶乘
void init(){
f[0] = 1;
f[1] = 1;
for(int i = 2; i < N; i++){
f[i] = f[i - 1] * i % mod;
}
}
//快速幂
ll qpow(ll a, ll b){
ll res = 1;
while(b){
if(1 & b){
res = res * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return res;
}
//求组合数
ll C(int n,int m){
return f[n] * qpow(f[m]*f[n - m] % mod,mod - 2) % mod ;
}
//Lucas定理
ll Lucas(ll n,ll m){
if(!m)
return 1;
return C(n % mod,m % mod) * Lucas(n / mod,m / mod) % mod;
}
int main(){
scanf("%d",&cas);
init();
int icas = 1;
while(cas--){
scanf("%d %d",&n,&k);
printf("Case %d: %lldn",icas++,Lucas(n,k));
}
return 0;
}
H - How Many Points?——扩展欧几里得
题意
在二维网格中，给定两个点 A , B A,B A,B的坐标，问线段 A , B A,B A,B上有多少个网格点？
思路
设
A
(
a
1
,
b
1
)
,
B
(
a
2
,
b
2
)
A(a_1,b_1),B(a_2,b_2)
A(a1,b1),B(a2,b2)，点
N
(
x
,
y
)
N(x,y)
N(x,y)在线段
A
B
AB
AB上，那么必然有
x
−
a
1
y
−
b
1
=
x
−
a
2
y
−
b
2
displaystylefrac{x-a_1}{y-b_1}=frac{x-a_2}{y-b_2}
y−b1x−a1=y−b2x−a2
可得
(
x
−
a
1
)
(
y
−
b
2
)
=
(
x
−
a
2
)
(
y
−
b
1
)
displaystyle(x-a_1)(y-b_2)=(x-a_2)(y-b_1)
(x−a1)(y−b2)=(x−a2)(y−b1)
x
y
−
a
1
y
−
b
2
x
+
a
1
b
2
=
x
y
−
a
2
y
−
b
1
x
+
a
2
b
1
displaystyle xy-a_1y-b_2x+a_1b_2=xy -a_2y-b_1x+a_2b_1
xy−a1y−b2x+a1b2=xy−a2y−b1x+a2b1
(
b
1
−
b
2
)
x
+
(
a
2
−
a
1
)
y
=
a
2
b
1
−
a
1
b
2
displaystyle (b_1-b_2)x+(a_2-a_1)y=a_2b_1-a_1b_2
(b1−b2)x+(a2−a1)y=a2b1−a1b2
令
(
b
1
−
b
2
)
=
A
′
,
(
a
2
−
a
1
)
=
B
′
,
a
2
b
1
−
a
1
b
2
=
C
′
(b_1-b_2) = A^{'},(a_2-a_1) = B^{'},a_2b_1-a_1b_2 = C^{'}
(b1−b2)=A′,(a2−a1)=B′,a2b1−a1b2=C′
A
′
x
+
B
′
y
=
C
′
displaystyle A^{'}x+B^{'}y=C^{'}
A′x+B′y=C′
到此我们的扩展欧几里得的模型就出来了。
我们要算有多少组满足在 A , B A,B A,B之间的解，分别求出满足条件的 x ， y x，y x，y的个数，取两者的最小值即可。
以求
x
x
x 的解的个数为例，
y
y
y 同理：
x
x
x 的通解为
x
=
k
∗
B
′
/
g
c
d
(
A
′
,
B
′
)
+
x
0
x = k*B^{'}/gcd(A^{'},B^{'})+x_0
x=k∗B′/gcd(A′,B′)+x0
那么在 A B AB AB之间的 x x x 值就是 a 1 + k ∗ B ′ / g c d ( A ′ , B ′ ) a_1+k*B^{'}/gcd(A^{'},B^{'}) a1+k∗B′/gcd(A′,B′)
那么，满足条件的 x x x的个数就是 ( a 2 − a 1 ) / ( B ′ / g c d ( A ′ , B ′ ) ) + 1 (a_2 - a_1) / (B^{'}/gcd(A^{'},B^{'})) + 1 (a2−a1) / (B′/gcd(A′,B′))+1，加的 1 1 1 是 A A A点。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
ll cas,a1,b1,a2,b2;
ll exgcd(ll a,ll b, ll &x, ll &y){
if(b == 0){
x = 1; y = 0; return a;
}
ll t = exgcd(b,a%b,x,y);
ll x0 = x,y0 = y;
x = y0;
y = x0 - a / b * y0;
return t;
}
int main(){
scanf("%lld",&cas);
int icas = 1;
while(cas--){
scanf("%lld %lld %lld %lld",&a1,&b1,&a2,&b2);
ll A = b1 - b2, B = a2 - a1,C = a2*b1 - a1*b2,x,y,x0;
ll g = exgcd(A,B,x,y);
if(A == 0){
printf("Case %d: %lldn",icas++,abs(B)+1);
continue;
}
if(B == 0){
printf("Case %d: %lldn",icas++,abs(A)+1);
continue;
}
if(C % g != 0){
printf("Case %d: 2n",icas++);
continue;
}
//printf("A = %lld B = %lld C = %lldn",A,B,C);
A /= g;
B /= g;
C /= g;
//printf("A = %lld B = %lld C = %lldn",A,B,C);
//x0 = (x * C % B + B) % B
ll ans = min(abs(a2 - a1) / abs(B),abs(b2 - b1) / abs(A));
printf("Case %d: %lldn",icas++,ans + 1);
}
return 0;
}
I - Trailing Zeroes (II)——分解因子
题意
求 c n r ∗ p q displaystyle c_n^r*p^q cnr∗pq的后导0的个数。
思路
后缀 0 0 0 的个数就是因子 2 2 2 和 5 5 5的个数。所以我们的目的就是分解出因子 2 , 5 2,5 2,5 ，提前预处理出 0 0 0~ M a x Max Max 的所有数的因子 2 2 2 和 5 5 5，保存下来，然后求一个前缀和。
然后求出整个式子因子 2 2 2和 5 5 5的个数：
式子中因子 2 2 2 的个数：
ans2[n] - ans2[r] - ans2[n - r] + tow[p]*q;
式子中因子 5 5 5 的个数：
ans[n] - ans[r] - ans[n - r] + five[p]*q;
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
int cas,n,r,p,q;
int ans[N],five[N],tow[N],ans2[N];
void init(){
for(int i = 1; i < N; i++){
int tmp = i;
while(tmp % 2 == 0 ){
tow[i]++;
tmp /= 2;
}
tmp = i;
while(tmp % 5 == 0 ){
five[i]++;
tmp /= 5;
}
}
for(int i = 1; i < N; i++){
ans[i] = ans[i-1] + five[i];
ans2[i] = ans2[i-1] + tow[i];
}
}
ll solve(){
ll res1,res ;
res = ans[n] - ans[r] - ans[n - r] + five[p]*q;
res1 = ans2[n] - ans2[r] - ans2[n - r] + tow[p]*q;
return min(res,res1);
}
int main(){
scanf("%d",&cas);
init();
int icas = 1;
while(cas--){
scanf("%d %d %d %d",&n,&r,&p,&q);
printf("Case %d: %lldn",icas++,solve());
}
return 0;
}
J - A New Function ——因子和
题意
f
(
i
)
f(i)
f(i) 表示
i
i
i 的的因子和 ，现要求出
∑
i
=
1
n
f
(
i
)
displaystylesum_{i=1}^{n}f(i)
i=1∑nf(i)。
思路
一个小知识点：
[
1
,
n
]
[1,n]
[1,n] 中因子中含有
i
i
i 的数字个数为
⌊
n
i
⌋
displaystylelfloorfrac{n}{i}rfloor
⌊in⌋。
我们来简单证明一下：
[ 1 , n ] 中 第 一 个 因 子 包 含 i 的 一 定 是 i 本 身 ， 那 么 第 二 个 因 子 包 含 i 的 就 是 2 ∗ i ， 第 三 个 就 是 3 ∗ i . . . 一 直 到 k ∗ i ， k ∗ i < = n , 所 以 [ 1 , n ] 中 一 共 有 ⌊ n i ⌋ 个 i 的 倍 数 。 [1,n]中第一个因子包含i的一定是i本身，那么第二个因子包含i的就是2*i，第三个就是3*i...一直到k*i，k*i<=n,所以[1,n]中一共有lfloorfrac{n}{i}rfloor个i的倍数。 [1,n]中第一个因子包含i的一定是i本身，那么第二个因子包含i的就是2∗i，第三个就是3∗i...一直到k∗i，k∗i<=n,所以[1,n]中一共有⌊in⌋个i的倍数。
那么我们的问题就转化为 ∑ i = 2 n ( ⌊ n i ⌋ − 1 ) ∗ i [ i ∣ n ] displaystylesum_{i =2}^{n}(lfloorfrac{n}{i}rfloor-1)*i[i | n] i=2∑n(⌊in⌋−1)∗i[i ∣ n]
直接数论整除分块解决
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll unsigned long long
using namespace std;
int cas,n;
ll solve(){
ll res = 0;
for(ll l = 2,r; l <= n; l = r + 1){
r = n / (n / l);
res += (r * (r + 1) / 2 - l *(l-1) / 2) * (n / l - 1);
}
return res;
}
int main(){
scanf("%d",&cas);
int icas = 1;
while(cas--){
scanf("%d",&n);
printf("Case %d: %llun",icas++,solve());
}
return 0;
}
K - False Ordering
题意
按照以下规则重新排序：
- 因子个数多数的放前面。
- 因子个数相同时，数字大的放前面。
思路
数据规模较小，直接记录每个数字的因子个数，保存在结构体中，重写排序函数，直接sort();
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
const int N = 1001;
struct Div_cnt{
int num , sum;
}div_cnt[N];
int prime[N],prime_tot = 0;
bool prime_tag[N] = {0};
int cas,icas = 1,n,cnt = 1;
bool cmp (const Div_cnt &a,const Div_cnt &b){
if(a.sum == b.sum) return a.num > b.num;
return a.sum < b.sum;
}
void solve(){
for(int i = 1; i < N; i++){
div_cnt[i].num = i;
div_cnt[i].sum = 0;
for(int j = 1 ; j * j <= i && j < N; j++)
if(i % j == 0){
if(j * j == i){
div_cnt[i].sum += 1;
}else
div_cnt[i].sum += 2;
}
}
sort(div_cnt + 1,div_cnt + N,cmp);
}
int main(){
solve();
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
printf("Case %d: %dn",icas++,div_cnt[n].num);
}
return 0;
}
L - Trailing Zeroes (III)——约数 和 二分答案
题意
给定一个
q
q
q，求一个数
n
!
n!
n!，需要满足
n
!
n!
n!有
q
q
q个后缀
0
0
0，要求
n
n
n尽量小。
思路
此题已经在[kuangbin] 专题十四 写过了 使用约数性质和二分答案解题。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const ll Max = 9e8 + 10;
ll cas,q;
bool check(ll n){
ll res = 0;
while(n){
res += n / 5;
n /= 5;
}
//cout<<"res = "<<res<<"n";
if(res >= q)
return true;
else
return false;
}
ll Erfen(ll l, ll r){
while(l <= r){
ll mid = (l + r) >> 1;
//cout<<"l = "<<l<<" mid = "<<mid<<" r = "<<r<<"n";
if(check(mid)) r = mid - 1;
else l = mid + 1;
}
return l;
}
int main(){
scanf("%lld",&cas);
for(int c = 1; c <= cas; c++){
scanf("%lld",&q);
ll ans = Erfen(1,Max);
ll cnt = 0,t = ans;
while(t){
cnt += t / 5;
t /= 5;
}
if(q != cnt){
printf("Case %d: impossiblen",c);
}else{
printf("Case %d: %lldn",c,ans);
}
}
return 0;
}
M - Bank Robbery ——解方程
题意
给出
A
−
B
A-B
A−B，并且已知
B
=
⌊
A
⌋
B=lfloor Arfloor
B=⌊A⌋，要求求出符合条件的
A
A
A，多个按字典序排列。
思路
已知
A
−
B
=
n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
(
1
)
A-B =n...................(1)
A−B=n...................(1)
A
/
10
=
B
A/10 = B
A/10=B
设
A
−
B
∗
10
=
x
.
.
.
.
.
.
.
.
.
.
.
.
(
2
)
A - B * 10 = x............(2)
A−B∗10=x............(2)
可知 x x x的范围为 0 0 0~ 9 9 9
结合
(
1
)
(
2
)
(1)(2)
(1)(2)两式可得
n
−
x
=
9
B
n - x=9B
n−x=9B
n
n
n是给定的所以我们只需要从
9
9
9~
0
0
0 枚举
x
x
x判断
n
−
x
n-x
n−x 是否是
9
9
9 的倍数即可，倒着枚举是为了输出顺序。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll unsigned long long
using namespace std;
ll cas,n,icas = 1;
int main(){
scanf("%llu",&cas);
while(cas--){
scanf("%llu",&n);
printf("Case %llu:",icas++);
for(int i = 9 ; i >= 0; i--){
if((n - i) % 9 == 0)
printf(" %llu",(n - i) / 9 * 10 + i);
}
}
return 0;
}
N - Help Hanzo——区间筛法
题意
给定区间
[
a
,
b
]
[a,b]
[a,b]，问
[
a
,
b
]
[a,b]
[a,b]中有多少素数。
思路
同是[kuangbin] 专题十四 的题目。
使用区间筛法
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
int icas = 1;
ll cas,a,b;
ll prime[N],prime_tot = 0;
bool prime_tag[N],bk[N];
void get_prime(){
for(int i = 2; i < N; i++){
if(!prime_tag[i]){
prime[prime_tot++] = i;
}
for(int j = 0 ; j < prime_tot && i * prime[j] < N; j++){
prime_tag[i * prime[j]] = true;
if(i % prime[j] == 0)
break;
}
}
}
ll solve(){
for(int i = 0; i <= b - a; i++) bk[i] = true;
for(int i = 0 ; i < prime_tot; i++){
ll tmp = a / prime[i] * prime[i];
if(tmp < a ) tmp += prime[i];
if(tmp < prime[i]*prime[i]) tmp = prime[i]*prime[i];
while(tmp <= b){
//printf("tmp = %dn",tmp);
bk[tmp - a] = false;
tmp += prime[i];
}
}
ll res = 0;
for(int i = 0 ; i <= b - a; i++)
if(bk[i]) res++;
if(a == 1)
res--;
return res;
}
int main(){
get_prime();
scanf("%lld",&cas);
while(cas--){
scanf("%lld %lld",&a,&b);
printf("Case %d: %lldn",icas++,solve());
}
return 0;
}
O - Fantasy of a Summation ——思维
题意
给出n,K,MOD，问下面这个程序中的res值为多少。
#include <stdio.h>
int cases, caseno;
int n, K, MOD;
int A[1001];
int main() {
scanf("%d", &cases);
while( cases-- ) {
scanf("%d %d %d", &n, &K, &MOD);
int i, i1, i2, i3, ... , iK;
for( i = 0; i < n; i++ ) scanf("%d", &A[i]);
int res = 0;
for( i1 = 0; i1 < n; i1++ ) {
for( i2 = 0; i2 < n; i2++ ) {
for( i3 = 0; i3 < n; i3++ ) {
...
for( iK = 0; iK < n; iK++ ) {
res = ( res + A[i1] + A[i2] + ... + A[iK] ) % MOD;
}
...
}
}
}
printf("Case %d: %dn", ++caseno, res);
}
return 0;
}
思路
同是[kuangbin] 专题十四 的题目。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll cas,n,k,m,val;
ll qpow(ll a,ll b,ll mod){
ll res = 1;
while(b){
if(b & 1){
res = (res * a) % mod;
}
a = (a * a) % mod;
b >>= 1;
}
return res;
}
int main(){
scanf("%lld",&cas);
for(int c = 1; c <= cas; c++){
ll sum = 0;
scanf("%lld %lld %lld",&n,&k,&m);
ll ans = qpow(n,k-1,m);
for(int i = 0 ; i < n; i++){
scanf("%lld",&val);
sum = (sum + val) % m;
}
ans = (k * sum) % m * ans % m;
printf("Case %d: %lldn",c,ans);
}
return 0;
}
P - Large Division——模拟大整数取余
题意
给两个数 A , B A,B A,B， A A A很大， B B B在整数范围。判断 B B B能不能整除 A A A。
思路
模拟 A A A整除 B B B的过程。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
string a;
ll b,cas ,icas = 1;
int main() {
ios::sync_with_stdio(false);
cin>>cas;
while(cas--) {
cin>>a>>b;
b = abs(b);
ll sum = 0,len = a.length();
int i;
if(a[0] == '-') i = 1;
else i = 0;
for(; i < len; i++) {
sum = sum * 10 + a[i] - '0';
sum = sum % b;
}
if(sum == 0){
cout<<"Case "<<icas++<<": divisiblen";
}else{
cout<<"Case "<<icas++<<": not divisiblen";
}
}
return 0;
}
Q - Finding LCM——唯一分解定理
题意
已知 L C M ( a , b , c ) = L . LCM (a, b, c) = L. LCM(a,b,c)=L. ，给定 a , b , L a,b,L a,b,L，求满足条件的最小的 c c c。
思路
利用唯一分解定理和最小公倍数的一个性质：
令：
a
=
p
1
c
1
∗
p
2
c
2
∗
.
.
.
∗
p
m
c
m
a = p_1^{c_1}*p_2^{c_2}*...*p_m^{c_m}
a=p1c1∗p2c2∗...∗pmcm
b
=
p
1
d
1
∗
p
2
d
2
∗
.
.
.
∗
p
m
d
m
b = p_1^{d_1}*p_2^{d_2}*...*p_m^{d_m}
b=p1d1∗p2d2∗...∗pmdm
则
l
c
m
(
a
,
b
)
=
p
1
m
a
x
(
c
1
,
d
1
)
∗
p
2
m
a
x
(
c
2
,
d
2
)
∗
.
.
.
∗
p
m
m
a
x
(
c
m
,
d
m
)
lcm(a,b) = p_1^{max(c_1,d_1)}* p_2^{max(c_2,d_2)}*...* p_m^{max(c_m,d_m)}
lcm(a,b)=p1max(c1,d1)∗p2max(c2,d2)∗...∗pmmax(cm,dm)
将
l
c
m
(
a
,
b
)
,
L
lcm(a,b),L
lcm(a,b),L 分别分解质因数为
∑
i
m
q
i
k
i
displaystylesum_i^mq_i^{k_i}
i∑mqiki 和
∑
i
n
p
i
c
i
displaystylesum_i^np_i^{c_i}
i∑npici，枚举每一项质因子，如果该项上质因子的次方不是最大值，我们就乘上一个该质因子的最大次幂，进行累乘，这样最终累乘的结果就是答案。
例如：
a
=
2
,
b
=
3
,
L
=
18
,
l
c
m
(
a
,
b
)
=
6
a = 2,b =3,L =18,lcm(a,b) = 6
a=2,b=3,L=18,lcm(a,b)=6
可分解成
l
c
m
(
a
,
b
)
=
2
1
×
3
1
lcm(a,b) = 2^1times3^1
lcm(a,b)=21×31
L
=
2
1
×
3
2
L =2^1times 3^2
L=21×32
初始
a
n
s
=
1
ans =1
ans=1，枚举到质因子
3
3
3的时候，累乘上一个
3
2
=
9
3^2=9
32=9
最后得
a
n
s
=
9
ans = 9
ans=9
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
ll a,b,cas,icas = 1,l;
int c[N] = {0}, ans[N] = {0};
int prime[N],prime_tot = 0,p[N],cnt = 0;
bool prime_tag[N] = {0};
ll gcd(ll a, ll b){
return b == 0 ? a : gcd(b,a%b);
}
ll lcm(ll a, ll b){
return a * b / gcd(a,b);
}
void get_prime() {
for(int i = 2; i < N; i++) {
if(!prime_tag[i]) {
prime[prime_tot++] = i;
}
for(int j = 0 ; j < prime_tot && i * prime[j] < N; j++) {
prime_tag[i * prime[j]] = true;
if(i % prime[j] == 0) break;
}
}
}
ll qpow(ll a,ll b) {
ll res = 1;
while(b) {
if(b & 1) res = res * a;
a = a * a;
b /= 2;
}
return res;
}
void divide1(ll n) {
for(int i = 0 ; i < prime_tot; i++) {
if(n % prime[i] == 0) {
c[prime[i]]= 0;
while(n % prime[i] == 0 && n > 1) {
c[prime[i]]++;
n /= prime[i];
//intf("yes ");
}
}
if(n == 1) break ;
}
}
void divide2(ll n) {
for(int i = 0 ; i < prime_tot; i++) {
if(n % prime[i] == 0) {
p[++cnt] = prime[i];
ans[prime[i]]= 0;
while(n % prime[i] == 0 && n > 1) {
ans[prime[i]]++;
n /= prime[i];
//intf("yes ");
}
}
if(n == 1) break ;
}
}
ll solve(ll n) {
divide1(n);
ll res = 1;
for(int i = 1 ; i <= cnt; i++) {
if(ans[p[i]] > c[p[i]]){
res *= qpow(p[i],ans[p[i]]);
}
}
return res ;
}
int main() {
get_prime();
scanf("%lld",&cas);
while(cas--) {
ll ans1,ans2;
scanf("%lld %lld %lld",&a,&b,&l);
cnt = 0;
printf("Case %d: ",icas++);
memset(ans,0,sizeof(ans));
memset(p,0,sizeof(p));
memset(c,0,sizeof(c));
if(l % a != 0 || l % b != 0) {
printf("impossiblen");
continue;
}
divide2(l);
ans1 = solve(lcm(a,b));
printf("%lldn",ans1);
}
return 0;
}
/*
1
24702 3202 1661011884
*/
R - Mysterious Bacteria——算术基本定理
题意
给一个
n
n
n，把
n
n
n表示为
b
p
b^p
bp的形式，问最大的
p
p
p的值是多少。
思路
算术基本定理分解 ，然后找出一个最大值。
但是，这一题有个坑，
n
n
n 可能是负数，这就要求
p
p
p 在
n
n
n 为复数的时候要是一个奇数。
所以如果一开始分解出来的
p
p
p是一个偶数，要一直除以2，直到变成一个奇数为止才是答案。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int Max = 1e6 + 10;
bool f[Max];
vector<int> prime;
ll cas,n;
void get_prime(){
for(int i = 2; i < Max; i++) f[i] = true;
for(ll i = 2; i < Max; i++){
for(ll j = i * i; j < Max; j += i){
f[j] = false;
}
}
for(int i = 2; i < Max; i++)
if(f[i]) prime.push_back(i);
}
ll divide(ll n){
ll c,ans = -1;
int len = prime.size();
for(int i = 0; i < len; i++){
c = 0;
while(n % prime[i] == 0 && n > 1){
n /= prime[i];
c++;
}
if(n == 1)
break;
}
if(n > 1) c = 1;
return c;
}
int main(){
get_prime();
scanf("%lld",&cas);
ll ans = 0;
for(int c = 1; c <= cas; c++){
scanf("%lld",&n);
if(n < 0){
ans = divide(-n);
while(ans % 2 == 0){
ans /= 2;
}
}else{
ans = divide(n);
}
printf("Case %d: %lldn",c,ans);
}
return 0;
}
S - Harmonic Number——调和级数
题意
求 f ( n ) = 1 / 1 + 1 / 2 + 1 / 3 + 1 / 4 … 1 / n ( 1 ≤ n ≤ 1 0 8 ) . f(n)=1/1+1/2+1/3+1/4…1/n (1 ≤ n ≤ 10^8). f(n)=1/1+1/2+1/3+1/4…1/n(1≤n≤108).，精确到 1 0 − 8 10^{-8} 10−8
思路
应用调和级数公式
#include <bits/stdc++.h>
using namespace std;
const int Max = 1e4 + 10;
const double r = 0.57721566490153286060651209;
double a[Max];
int cas,n;
void solve(){
a[0] = 0;
for(int i = 1; i < Max; i++){
a[i] = a[i-1] + 1.0/i;
}
}
int main(){
scanf("%d",&cas);
solve();
for(int c = 1; c <= cas; c++){
scanf("%d",&n);
if(n < Max)
printf("Case %d: %.10fn",c,a[n]);
else
printf("Case %d: %.10fn",c,log(n) + r + 1.0/(2*n));
}
return 0;
}
T - Pairs Forming LCM —— 唯一分解定理（算术分解定理）
同是[kuangbin] 专题十四 的题目。
题意
求出小于
n
n
n的数中，有多少数对的最小公倍数是
n
n
n。
思路
由算术分解定理可以求出最大公约数和最小公倍数：
对于两个整数
a
,
b
a,b
a,b
将
a
a
a分解：
a
=
p
1
e
1
p
2
e
2
p
3
e
3
.
.
.
p
m
e
m
a=p_1^{e_1}p_2^{e_2}p_3^{e_3}...p_m^{e_m}
a=p1e1p2e2p3e3...pmem
将 b b b分解： b = p 1 k 1 p 2 k 2 p 3 k 3 . . . p m k m b=p_1^{k_1}p_2^{k_2}p_3^{k_3}...p_m^{k_m} b=p1k1p2k2p3k3...pmkm
GCD（ a , b a,b a,b）= p 1 m i n ( e 1 , k 1 ) p 2 m i n ( e 2 , k 2 ) p 3 m i n ( e 3 , k 3 ) . . . p m m i n ( e m , k m ) p_1^{min(e_1,k_1)}p_2^{min(e_2,k_2)}p_3^{min(e_3,k_3)}...p_m^{min(e_m,k_m)} p1min(e1,k1)p2min(e2,k2)p3min(e3,k3)...pmmin(em,km)
LCM（ a , b a,b a,b）= p 1 m a x ( e 1 , k 1 ) p 2 m a x ( e 2 , k 2 ) p 3 m a x ( e 3 , k 3 ) . . . p m m a x ( e m , k m ) p_1^{max(e_1,k_1)}p_2^{max(e_2,k_2)}p_3^{max(e_3,k_3)}...p_m^{max(e_m,k_m)} p1max(e1,k1)p2max(e2,k2)p3max(e3,k3)...pmmax(em,km)
再将GCD( a , b a,b a,b)分解：GCD( a , b a,b a,b) = p 1 c 1 p 2 c 2 p 3 c 3 . . . p m c m =p_1^{c_1}p_2^{c_2}p_3^{c_3}...p_m^{c_m} =p1c1p2c2p3c3...pmcm。
可知： c 1 = m a x ( e 1 , k 1 ) , c 2 = m a x ( e 2 , k 2 ) , . . . , c m = m a x ( e m , k m ) c_1 = max(e_1,k_1),c_2 = max(e_2,k_2),...,c_m = max(e_m,k_m) c1=max(e1,k1),c2=max(e2,k2),...,cm=max(em,km)
如果 e i = c i e_i = c_i ei=ci,那么 k i k_i ki 就可以取 [ 0 , e i ] [ 0,e_i] [ 0,ei]共 e i + 1 e_i+1 ei+1种情况
同时，对称的来说，如果 k i = c i k_i = c_i ki=ci,那么 e i e_i ei 就可以取 [ 0 , k i ] [ 0,k_i] [ 0,ki]共 k i + 1 k_i+1 ki+1种情况。
同时因为 k i = e i = c i k_i = e_i = c_i ki=ei=ci的情况被算了两次，所以要剪掉一次，这样一来第i项就一共有 2 ∗ c i + 1 2*c_i+1 2∗ci+1种情况了。
将每一项的情况相乘，就可以得出所有可能的情况，同时因为我们计算的时候是对称的，所以我们计算出的结果是真正结果的两倍。举个栗子：当 n = 4 n = 4 n=4的时候， a = 1 , b = 2 a=1,b = 2 a=1,b=2和 a = 2 , b = 1 a= 2,b=1 a=2,b=1其实是一种情况，同时因为 a = = b a==b a==b的情况我们只算了一次，所以要加上一次 a = = b a==b a==b的情况，保证所有情况都出现了两次，再统一除上 2 。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int Max = 1e7 + 10;
int cas;
bool f[Max];
vector<int> prime;
void get_prime(){
for(int i = 2; i < Max; i++) f[i] = true;
for(ll i = 2; i < Max; i++){
for(ll j = i * i; j < Max; j += i)
f[j] = false;
}
for(int i = 2; i < Max; i++)
if(f[i]) prime.push_back(i);
}
ll divide(ll n){
int len = prime.size();
ll e ,ans = 1;
//printf("len = %dn",len);
for(int i = 0 ; i < len; i++){
e = 0;
while(n % prime[i] == 0 && n > 1){
e++;
n /= prime[i];
}
ans *= (2 * e + 1) ;
if(n == 1)
break;
}
if(n > 1){
ans *= (2 * 1 + 1) ;
}
return (ans + 1) / 2;
}
int main(){
get_prime();
scanf("%d",&cas);
ll n;
for(int c = 1; c <= cas; c++){
scanf("%lld",&n);
printf("Case %d: %lldn",c,divide(n));
}
return 0;
}
U - Harmonic Number (II) —— 数论整除分块
同是[kuangbin] 专题十四 的题目。
题意
给出
n
n
n ，求和：
n
/
1
+
n
/
2
+
n
/
3
+
.
.
.
+
n
/
n
n/1 + n/2+n/3+...+n/n
n/1+n/2+n/3+...+n/n。
思路
原本是抄网上的思路，后来仔细一想 这不是就是整除分块吗？直接一首模板
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
int cas , icas = 1;
ll n;
ll solve(ll n){
ll res = 0;
for(ll l = 1, r; l <= n; l = r + 1){
r = n / (n / l);
res += (r - l + 1) * (n / l);
//printf("l = %lld r = %lld ans = %lldn",l,r,(r - l + 1) * (n / l));
}
return res;
}
int main(){
scanf("%d",&cas);
while(cas--){
scanf("%lld",&n);
printf("Case %d: %lldn",icas++,solve(n));
}
return 0;
}
V - Goldbach`s Conjecture ——素数
同是[kuangbin] 专题十四 的题目。
题意：
给出几组测试数据，每组给出一个n，问n能被分成几对素数的和。
思路：
先打表，求出所有的素数。从小到大枚举所有素数，对于当前枚举的素数a，看n - a是否也是一个素数，如果是的话，就计数，求出答案。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int Max = 1e7 + 10;
bool f[Max];
int prime[666666];
int cas,n,len = 0;
void get_prime(){
for(int i = 2; i < Max; i++) f[i] = 1;
for(ll i = 2; i < Max; i++){
for(ll j = i * i; j < Max; j += i){
f[j] = 0;
}
}
for(int i = 2; i < Max; i++)
if(f[i]) prime[len++] = i;
}
int main(){
get_prime();
scanf("%d",&cas);
for(int c = 1; c <= cas; c++){
int ans = 0;
scanf("%d",&n);
for(int i = 0; i < len; i++){
if(prime[i] > n/2)
break;
if(f[n - prime[i]]){
ans++;
}
}
printf("Case %d: %dn",c,ans);
}
return 0;
}
W - Sum of Consecutive Integers —— 求奇因子个数
题意
给定一个数 N N N，可以被分解成多个连续数的和，问有多少中分解的方法？
例如, N = 15 N = 15 N=15 有 3 个解, ( 1 + 2 + 3 + 4 + 5 ) , ( 4 + 5 + 6 ) , ( 7 + 8 ) . (1+2+3+4+5), (4+5+6), (7+8). (1+2+3+4+5),(4+5+6),(7+8).
思路
我们先设 分解成连续的 k k k 个数，第一项为 x x x ,根据等差数列的求和公式可以知道
s u m = k ∗ x + k ( k − 1 ) / 2 = N sum = k*x+k(k-1)/2=N sum=k∗x+k(k−1)/2=N
我们整理一下：
k ∗ ( 2 ∗ x + k − 1 ) = 2 N k*(2*x+k-1)=2N k∗(2∗x+k−1)=2N
这样一来我们可以得出一个结论：
-
k
k
k 一定是一个奇数，并且是
N
N
N的一个因子。
所以我们的问题就转化成了一个：求 N N N 有多少个奇因子的个数。
根据唯一分解定理的推论：
N
N
N的正约数个数为（
∏
prod
∏表示连乘）
(
c
1
+
1
)
∗
(
c
2
+
1
)
∗
.
.
.
∗
(
c
m
+
1
)
=
∏
i
=
1
m
(
c
i
+
1
)
(c_1+1)*(c_2+1)*...*(c_m+1)=displaystyleprod^m_{i=1} (c_i+1)
(c1+1)∗(c2+1)∗...∗(cm+1)=i=1∏m(ci+1)
因为要求是奇因子，我们只需要不乘第一个因子 2 2 2，就是奇因子。所以我们去掉 2 c 1 2^{c_1} 2c1中的 c 1 c_1 c1，和出现 1 1 1的情况，即所有的 c i c_i ci都取 0 0 0 的情况，剩下的就是答案了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
const int N = 1e7 + 5;
int cas,icas = 1;
ll n;
ll prime[666666];
int prime_tot = 0;
bool prime_tag[N] = {0};
void get_prime(){
for(ll i = 2ll; i < N; i++){
if(!prime_tag[i]){
prime[prime_tot++] = i;
}
for(ll j = 0; j < prime_tot && i * prime[j] < N; j++){
prime_tag[i * prime[j]] = true;
if(i % prime[j] == 0) break;
}
}
}
ll solve(ll n) {
ll res = 1;
for(ll i = 0; i < prime_tot && prime[i] * prime[i] <= n; i++){
ll c = 0;
while(n % prime[i] == 0 && n > 1){
c++;
n /= prime[i];
}
if(i != 0)
res *= c + 1;
if(n == 1) break;
}
if(n > 2)
res *= 2;
res--;
return res;
}
int main() {
get_prime();
scanf("%d",&cas);
while(cas--) {
scanf("%lld",&n);
printf("Case %d: %lldn",icas++,solve(n));
}
return 0;
}
最后
以上就是光亮夏天为你收集整理的[kuangbin]数学训练四 数论 [Cloned]的全部内容，希望文章能够帮你解决[kuangbin]数学训练四 数论 [Cloned]所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
![[kuangbin]数学训练四 数论 [Cloned]](/uploads/reation/bcimg10.png)
发表评论 取消回复