文章目录
C Looooops
description
solution
将题意转化为数学式子表示 A + C x ≡ B ( m o d 2 k ) A+Cx\equiv B\pmod {2^k} A+Cx≡B(mod2k)，最后就是求最小的 x x x
其实将取模操作去掉就是非常模板的扩展欧几里得， C ⋅ x − y ⋅ 2 k = B − A C·x-y·2^k=B-A C⋅x−y⋅2k=B−A
先求出一组特解，然后求出最小正整数 x x x（最小解法请传送至证明章）
code
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define int long long
int exgcd( int a, int b, int &x, int &y ) {
if( ! b ) {
x = 1, y = 0;
return a;
}
else {
int d = exgcd( b, a % b, y, x );
y -= ( a / b ) * x;
return d;
}
}
signed main() {
int A, B, C, k;
while( scanf( "%lld %lld %lld %lld", &A, &B, &C, &k ) ) {
if( ! A && ! B && ! C && ! k ) break;
int a = C, b = 1ll << k, c = B - A, x, y;
int d = exgcd( a, b, x, y );
if( c % d ) {
printf( "FOREVER\n" );
continue;
}
x = ( x * ( c / d ) % ( b / d ) + ( b / d ) ) % ( b / d );
printf( "%lld\n", x );
}
return 0;
}
跳跳棋
description
solution
此题的关键在于，一次只允许跳过1颗棋子
也就是对于中间的棋子而言，只能是离之最近的棋子才有跳的权利
a,b,c
→
\rightarrow
→b,2b-a,c/a,2b-c,b
如果将 ( a , b , c ) (a,b,c) (a,b,c)看成一个点，那么一个点只会有两种后继
建二叉树，奉行全都相对中间棋子进行跳跃，缩小三个球的距离直到相等，把这类点定义为树的根
判断无解，只需要看初始局面和结束局面是否按照以上规则操作后隶属于同一节点
跳跃一次，就是在树上爬一层，不能一步一步爬，而是一次性跳成距离更短的点，然后换另外一边跳
再这过程中统计局面跳了多少步，也就是对应的深度
将初始局面和结束局面先跳到同一层，然后再二分跳的深度找 l c a lca lca（两局面相同）
code
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
#define inf 1e18
struct node {
int pos[5];
bool operator != ( const node &t ) const {
for( int i = 1;i <= 3;i ++ )
if( pos[i] != t.pos[i] ) return 1;
return 0;
}
}S, E;
int dep_S, dep_E, dep;
int Sp[5], Ep[5];
node solve( int MS[], int len ) {
node ans;
for( int i = 1;i <= 3;i ++ )
ans.pos[i] = MS[i];
int d1 = MS[2] - MS[1], d2 = MS[3] - MS[2];
if( d1 == d2 ) return ans;
else if( d1 < d2 ) {
int k = min( len, ( d2 - 1 ) / d1 );
len -= k, dep += k;
ans.pos[1] += k * d1;
ans.pos[2] += k * d1;
}
else {
int k = min( len, ( d1 - 1 ) / d2 );
len -= k, dep += k;
ans.pos[2] -= k * d2;
ans.pos[3] -= k * d2;
}
if( len ) return solve( ans.pos, len );
else return ans;
}
signed main() {
for( int i = 1;i <= 3;i ++ )
scanf( "%lld", &Sp[i] );
for( int i = 1;i <= 3;i ++ )
scanf( "%lld", &Ep[i] );
sort( Sp + 1, Sp + 4 );
sort( Ep + 1, Ep + 4 );
S = solve( Sp, inf );
dep_S = dep;
dep = 0;
E = solve( Ep, inf );
dep_E = dep;
dep = 0;
if( S != E ) return ! printf( "NO\n" );
else printf( "YES\n" );
if( dep_S > dep_E ) {
swap( dep_S, dep_E );
for( int i = 1;i <= 3;i ++ )
swap( Sp[i], Ep[i] );
}
int ans = dep_E - dep_S;
if( ans ) {
E = solve( Ep, ans );
for( int i = 1;i <= 3;i ++ )
Ep[i] = E.pos[i];
}
int l = 0, r = dep_S;
while( l < r ) {
int mid = ( l + r ) >> 1;
if( solve( Sp, mid ) != solve( Ep, mid ) ) l = mid + 1;
else r = mid;
}
printf( "%lld\n", ans + l * 2 );
return 0;
}
The Luckiest number
description
solution
L ∣ 8 ∗ 1 0 n − 1 9 ⇔ 9 ∗ L gcd ( 8 , L ) ∣ ( 10 n − 1 ) ∗ 8 gcd ( 8 , L ) L\bigg|8*\frac{10^n-1}{9}\Leftrightarrow \frac{9*L}{\gcd(8,L)}\bigg|\frac{(10n-1)*8}{\gcd(8,L)} L∣∣∣∣8∗910n−1⇔gcd(8,L)9∗L∣∣∣∣gcd(8,L)(10n−1)∗8
∵ gcd ( 8 , 9 ) = 1 \because \gcd(8,9)=1 ∵gcd(8,9)=1
∴ 10 n ≡ 1 ( m o d 9 L gcd ( 8 , L ) ) \therefore 10n\equiv 1\pmod{\frac{9L}{\gcd(8,L)}} ∴10n≡1(modgcd(8,L)9L)
无解，即为 gcd ( 10 , 9 L gcd ( 8 , L ) ) = 1 \gcd(10,\frac{9L}{\gcd(8,L)})=1 gcd(10,gcd(8,L)9L)=1
否则转化为 a x ≡ 1 ( m o d m ) a^x\equiv 1\pmod m ax≡1(modm)，求最小的 x x x
根据阶的公式有 x ∣ ϕ ( m ) x\bigg|\phi(m) x∣∣∣∣ϕ(m)
直接枚举计算
code
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define int long long
int gcd( int x, int y ) {
if( ! y ) return x;
else return gcd( y, x % y );
}
int calc( int x ) {
int ans = x;
for( int i = 2;i * i <= x;i ++ )
if( x % i == 0 ) {
ans = ans / i * ( i - 1 );
while( x % i == 0 ) x /= i;
}
if( x != 1 ) ans = ans / x * ( x - 1 );
return ans;
}
int qkmul( int x, int y, int mod ) {
int ans = 0;
while( y ) {
if( y & 1 ) ans = ( ans + x ) % mod;
x = ( x + x ) % mod;
y >>= 1;
}
return ans;
}
int qkpow( int x, int y, int mod ) {
int ans = 1;
while( y ) {
if( y & 1 ) ans = qkmul( ans, x, mod );
x = qkmul( x, x, mod );
y >>= 1;
}
return ans;
}
signed main() {
int L;
for( int T = 1;;T ++ ) {
scanf( "%lld", &L );
if( ! L ) return 0;
L *= 9;
for( int i = 1;i <= 3;i ++ )
if( L % 2 == 0 ) L >>= 1;
else break;
if( gcd( 10, L ) != 1 ) {
printf( "Case %lld: 0\n", T );
continue;
}
int phi = calc( L ), ans = L;
for( int i = 1;i * i <= phi;i ++ )
if( phi % i ) continue;
else {
if( qkpow( 10, i, L ) == 1 ) {
ans = i;
break;
}
else if( qkpow( 10, phi / i, L ) == 1 )
ans = min( ans, phi / i );
}
printf( "Case %lld: %lld\n", T, ans );
}
return 0;
}
CF906D Power Tower
description
solution
扩展欧拉定理的板题
x
r
≡
{
x
r
r
<
m
x
r
%
ϕ
(
m
)
(
x
,
m
)
=
1
x
r
%
ϕ
(
m
)
+
ϕ
(
m
)
(
x
,
m
)
>
1
x^r\equiv \begin{cases} x^r&&r<m\\ x^{r\%\phi(m)}&&(x,m)=1\\ x^{r\%\phi(m)+\phi(m)}&&(x,m)>1 \end{cases}
xr≡⎩⎪⎨⎪⎧xrxr%ϕ(m)xr%ϕ(m)+ϕ(m)r<m(x,m)=1(x,m)>1
迭代计算指数，当前层
m
o
d
mod
mod的
ϕ
(
m
o
d
)
\phi(mod)
ϕ(mod)就是下一层其指数的
m
o
d
′
mod'
mod′
code
#include <iostream>
#include <cstdio>
using namespace std;
#if(__cplusplus == 201103L)
#include <unordered_map>
#else
#include <tr1/unordered_map>
namespace std
{
using std::tr1::unordered_map;
}
#endif
#define int long long
#define maxn 100005
unordered_map < int, int > mp;
int l, r;
int w[maxn];
int E( int x, int mod ) {
return x < mod ? x : x % mod + mod;
}
int qkpow( int x, int y, int mod ) {
int ans = 1;
while( y ) {
if( y & 1 ) ans = E( ans * x, mod );
x = E( x * x, mod );
y >>= 1;
}
return ans;
}
int phi( int n ) {
if( mp.count( n ) ) return mp[n];
int ans = n, x = n;
for( int i = 2;i * i <= x;i ++ )
if( x % i == 0 ) {
ans = ans / i * ( i - 1 );
while( x % i == 0 ) x /= i;
}
if( x != 1 ) ans = ans / x * ( x - 1 );
return mp[n] = ans;
}
int solve( int d, int pos, int mod ) {
if( pos == r + 1 || mod == 1 ) return E( d, mod );
int p = phi( mod );
int e = solve( w[pos], pos + 1, p );
return qkpow( d, E( e, p ), mod );
}
signed main() {
int n, mod, Q;
scanf( "%lld %lld", &n, &mod );
for( int i = 1;i <= n;i ++ )
scanf( "%lld", &w[i] );
scanf( "%lld", &Q );
while( Q -- ) {
scanf( "%lld %lld", &l, &r );
printf( "%lld\n", solve( w[l], l + 1, mod ) % mod );
}
}
Minimal Power of Prime
description
solution
一道数据范围极大的整数标准唯一分解板题
采用试除法
用不超过 n 1 5 n^\frac{1}{5} n51次方的质数去除 n n n，那么 n n n最多剩下四个质因数
条件语句大力讨论， n n n是不是二次幂/三次幂/四次幂，都不是那就一定属于至少一个是一次幂的情况
code
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define maxn 1000000
#define int long long
int T, n, cnt;
bool vis[maxn];
int prime[maxn];
void sieve() {
for( int i = 2;i < maxn;i ++ ) {
if( ! vis[i] ) vis[i] = 1, prime[++ cnt] = i;
for( int j = 1;j <= cnt && i * prime[j] < maxn;j ++ ) {
vis[i * prime[j]] = 1;
if( i % prime[j] == 0 ) break;
}
}
}
int calc( int x, int t ) {
int ans = 1;
for( int i = 1;i <= t;i ++ )
ans *= x;
return ans;
}
signed main() {
sieve();
scanf( "%lld", &T );
while( T -- ) {
scanf( "%lld", &n );
int m = powl( n, 1.0 / 5 ), ans = n;
for( int i = 1;i <= cnt;i ++ )
if( prime[i] > m ) break;
else if( n % prime[i] == 0 ) {
int tot = 0;
while( n % prime[i] == 0 )
tot ++, n /= prime[i];
ans = min( ans, tot );
}
int x = powl( n, 1.0 / 4 );
int y = powl( n, 1.0 / 3 );
int z = powl( n, 1.0 / 2 );
if( n == 1 ) goto print;
if( calc( x, 4 ) == n || calc( x - 1, 4 ) == n || calc( x + 1, 4 ) == n )
ans = min( ans, 4ll );
else if( calc( y, 3 ) == n || calc( y - 1, 3 ) == n || calc( y + 1, 3 ) == n )
ans = min( ans, 3ll );
else if( calc( z, 2 ) == n || calc( z - 1, 2 ) == n || calc( z + 1, 2 ) == n )
ans = min( ans, 2ll );
else
ans = min( ans, 1ll );
print :
printf( "%lld\n", ans );
}
return 0;
}
[SDOI2008]仪仗队
description
solution
定义每个点的坐标为 ( x − 1 , y − 1 ) (x-1,y-1) (x−1,y−1)，那么 C C C君就在 ( 0 , 0 ) (0,0) (0,0)位置上
考虑能被看到的小朋友的点坐标满足的性质
根据直线可以由向量刻画，设 ( x , y ) (x,y) (x,y)小朋友能被看到，那么这条直线上的 λ > 1 , ( λ x , λ y ) \lambda>1,(\lambda x,\lambda y) λ>1,(λx,λy)都会被挡住
且 gcd ( λ x , λ y ) = λ ( x , y ) ≥ λ > 1 \gcd(\lambda x,\lambda y)=\lambda(x,y)\ge \lambda>1 gcd(λx,λy)=λ(x,y)≥λ>1
也就是说，如果 gcd ( x , y ) > 1 \gcd(x,y)>1 gcd(x,y)>1该小朋友会被挡住
如果 gcd ( x , y ) = 1 \gcd(x,y)=1 gcd(x,y)=1的小朋友会被挡住，那么一定存在 ( x μ , y μ ) , μ > 1 (\frac{x}{\mu},\frac{y}{\mu}),\mu>1 (μx,μy),μ>1的小朋友存在，显然不存在这样的点
综上，当且仅当小朋友的横纵坐标互质的时候，才会被看见
转述成数学语言，即： a n s = ∑ i = 0 n − 1 ∑ j = 0 n − 1 [ gcd ( i , j ) = 1 ] ans=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\Big[\gcd(i,j)=1\Big] ans=∑i=0n−1∑j=0n−1[gcd(i,j)=1]
⇔ ∑ i = 0 n − 1 ∑ j = 0 i − 1 [ gcd ( i , j ) = 1 ] + ∑ i = 0 n − 1 ∑ j = i i [ gcd ( i , j ) = 1 ] + ∑ i = 0 n − 1 ∑ j = i + 1 n − 1 [ gcd ( i , j ) = 1 ] \Leftrightarrow \sum_{i=0}^{n-1}\sum_{j=0}^{i-1}\Big[\gcd(i,j)=1\Big]+\sum_{i=0}^{n-1}\sum_{j=i}^i\Big[\gcd(i,j)=1\Big]+\sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}\Big[\gcd(i,j)=1\Big] ⇔∑i=0n−1∑j=0i−1[gcd(i,j)=1]+∑i=0n−1∑j=ii[gcd(i,j)=1]+∑i=0n−1∑j=i+1n−1[gcd(i,j)=1]
∑ i = 0 n − 1 ∑ j = i i [ gcd ( i , j ) = 1 ] \sum_{i=0}^{n-1}\sum_{j=i}^i\Big[\gcd(i,j)=1\Big] ∑i=0n−1∑j=ii[gcd(i,j)=1]代表 y = x y=x y=x直线，显然只能看到一个小朋友，然后就可以删去了
n × n n\times n n×n的图， C C C君在原点处，隐藏的性质是看到的小朋友关于 y = x y=x y=x直线对称
式子继续化为 2 ( ∑ i = 0 n − 1 ∑ j = 0 i − 1 [ gcd ( i , j ) = 1 ] ) 2\bigg(\sum_{i=0}^{n-1}\sum_{j=0}^{i-1}\Big[\gcd(i,j)=1\Big]\bigg) 2(∑i=0n−1∑j=0i−1[gcd(i,j)=1])
惊奇的发现内层循环的取值范围以及要求完全符合欧拉函数 φ \varphi φ的定义
于是乎，最终答案成为 1 + 2 ∑ i = 0 n − 1 φ ( i ) 1+2\sum_{i=0}^{n-1}\varphi(i) 1+2∑i=0n−1φ(i)
code
#include <cstdio>
#define maxn 40005
int prime[maxn], phi[maxn];
bool vis[maxn];
int n;
void sieve() {
phi[1] = 1; int cnt = 0;
for( int i = 2;i <= n;i ++ ) {
if( ! vis[i] ) prime[++ cnt] = i, phi[i] = i - 1;
for( int j = 1;j <= cnt && i * prime[j] <= n;j ++ ) {
vis[i * prime[j]] = 1;
if( i % prime[j] == 0 ) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else
phi[i * prime[j]] = phi[i] * ( prime[j] - 1 );
}
}
}
int main() {
scanf( "%d", &n );
if( n == 1 ) return ! printf( "0\n" );
sieve();
int ans = 0;
for( int i = 0;i < n;i ++ )
ans += ( phi[i] << 1 );
printf( "%d\n", ans + 1 );
}
LCMSUM
description
solution
∑ i = 1 n lcm ( i , j ) ⇔ ∑ i = 1 n i × n gcd ( i , n ) \sum_{i=1}^n \operatorname{lcm}(i,j)\Leftrightarrow \sum_{i=1}^n\frac{i\times n}{\operatorname{gcd}(i,n)} ∑i=1nlcm(i,j)⇔∑i=1ngcd(i,n)i×n
∵ gcd ( i , n ) = gcd ( n − i , n ) \because \gcd(i,n)=\gcd(n-i,n) ∵gcd(i,n)=gcd(n−i,n)，两两 gcd \gcd gcd相同的合并 i + ( n − i ) = n i+(n-i)=n i+(n−i)=n
1 2 ( ∑ i = 1 n − 1 i ∗ n gcd ( i , n ) + ∑ i = n − 1 1 i ∗ n gcd ( i , n ) ) + lcm ( n , n ) = n + 1 2 ∑ i = 1 n − 1 n 2 gcd ( i , j ) \frac{1}{2}\Big(\sum_{i=1}^{n-1}\frac{i*n}{\gcd(i,n)}+\sum_{i=n-1}^1\frac{i*n}{\gcd(i,n)}\Big)+\operatorname{lcm}(n,n)=n+\frac{1}{2}\sum_{i=1}^{n-1}\frac{n^2}{\gcd(i,j)} 21(∑i=1n−1gcd(i,n)i∗n+∑i=n−11gcd(i,n)i∗n)+lcm(n,n)=n+21∑i=1n−1gcd(i,j)n2
gcd ( i , n ) = d \gcd(i,n)=d gcd(i,n)=d的 i i i的个数有 ϕ ( n d ) \phi(\frac{n}{d}) ϕ(dn)个 ( g c d ( i d , n d ) = 1 \Big(gcd(\frac{i}{d},\frac{n}{d})=1 (gcd(di,dn)=1的个数有 ϕ ( n d ) ) \phi(\frac{n}{d})\Big) ϕ(dn))
⇒ n + 1 2 ∑ i = 1 n − 1 n 2 gcd ( i , j ) = n + 1 2 ∑ d ∣ n n 2 ⋅ ϕ ( n d ) d = n + 1 2 ∑ d ∣ n n 2 ⋅ ϕ ( d ) n d \Rightarrow n+\frac{1}{2}\sum_{i=1}^{n-1}\frac{n^2}{\gcd(i,j)}=n+\frac{1}{2}\sum_{d\big|n}\frac{n^2·\phi(\frac{n}{d})}{d}=n+\frac{1}{2}\sum_{d\big|n}n^2·\frac{\phi(d)}{\frac{n}{d}} ⇒n+21∑i=1n−1gcd(i,j)n2=n+21∑d∣∣ndn2⋅ϕ(dn)=n+21∑d∣∣nn2⋅dnϕ(d)
= n + n ∑ d ∣ n d ⋅ ϕ ( d ) 2 =n+n\sum_{d\big|n}\frac{d·\phi(d)}{2} =n+n∑d∣∣n2d⋅ϕ(d)
线性筛预处理
code
#include <cstdio>
#define maxn 1000000
#define int long long
int prime[maxn + 5], phi[maxn + 5], sum[maxn + 5];
bool vis[maxn + 5];
void sieve() {
phi[1] = 1; int cnt = 0;
for( int i = 2;i <= maxn;i ++ ) {
if( ! vis[i] ) prime[++ cnt] = i, phi[i] = i - 1;
for( int j = 1;j <= cnt && i * prime[j] <= maxn;j ++ ) {
vis[i * prime[j]] = 1;
if( i % prime[j] == 0 ) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else
phi[i * prime[j]] = phi[i] * ( prime[j] - 1 );
}
}
for( int i = 1;i <= maxn;i ++ )
for( int j = 1;i * j <= maxn;j ++ )
sum[i * j] += i * phi[i] / 2;
for( int i = 1;i <= maxn;i ++ )
sum[i] = sum[i] * i + i;
}
signed main() {
sieve();
int T, n;
scanf( "%lld", &T );
while( T -- ) {
scanf( "%lld", &n );
if( n == 1 ) printf( "1\n" );
else printf( "%lld\n", sum[n] );
}
return 0;
}