文章目錄

• C Looooops
• • description
  • solution
  • code
• 跳跳棋
• • description
  • solution
  • code
• The Luckiest number
• • description
  • solution
  • code
• CF906D Power Tower
• • description
  • solution
  • code
• Minimal Power of Prime
• • description
  • solution
  • code
• [SDOI2008]儀仗隊
• • description
  • solution
  • code
• LCMSUM
• • description
  • solution
  • code

下文涉及到的所有數(shù)論知識證明傳送門1

下文涉及到的所有數(shù)論知識證明傳送門2

C Looooops

description

solution

將題意轉(zhuǎn)化為數(shù)學式子表示$A+Cx\equiv B(\mathrm{m}\mathrm{o}\mathrm{d}{2}^k)$，最后就是求最小的$x$

其實將取模操作去掉就是非常模板的擴展歐幾里得， $C?x?y?2^k=B?A$

先求出一組特解，然后求出最小正整數(shù)$x$（最小解法請傳送至證明章）

code

#include <cmath> #include <cstdio> #include <iostream> using namespace std; #define int long longint 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$\to$b,2b-a,c/a,2b-c,b

如果將$(a,b,c)$看成一個點，那么一個點只會有兩種后繼

建二叉樹，奉行全都相對中間棋子進行跳躍，縮小三個球的距離直到相等，把這類點定義為樹的根

判斷無解，只需要看初始局面和結(jié)束局面是否按照以上規(guī)則操作后隸屬于同一節(jié)點

跳躍一次，就是在樹上爬一層，不能一步一步爬，而是一次性跳成距離更短的點，然后換另外一邊跳

再這過程中統(tǒng)計局面跳了多少步，也就是對應的深度

將初始局面和結(jié)束局面先跳到同一層，然后再二分跳的深度找$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?\frac{10^n?1}{9}?\frac{9?L}{\gcd (8,L)}|\frac{(10n?1)?8}{\gcd (8,L)}$

$\because \gcd (8,9)=1$

$\therefore 10n\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}\frac{9L}{\gcd (8,L)})$

無解，即為$\gcd (10,\frac{9L}{\gcd (8,L)})=1$

否則轉(zhuǎn)化為$a^x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$，求最小的$x$

根據(jù)階的公式有$x|?(m)$

直接枚舉計算

code

#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define int long longint 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\equiv ?\begin{array}{llc}{x}^r& & r<m\\ x^{r\%?(m)}& & (x,m)=1\\ x^{r\%?(m)+?(m)}& & (x,m)>1\end{array}$$
迭代計算指數(shù)，當前層$mod$的$?(mod)$就是下一層其指數(shù)的$mo{d}^{\prime }$

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

一道數(shù)據(jù)范圍極大的整數(shù)標準唯一分解板題

采用試除法

用不超過$n^{\frac{1}{5}}$次方的質(zhì)數(shù)去除$n$，那么$n$最多剩下四個質(zhì)因數(shù)

條件語句大力討論，$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 );elseans = min( ans, 1ll );print : printf( "%lld\n", ans );}return 0; }

[SDOI2008]儀仗隊

description

solution

定義每個點的坐標為$(x?1,y?1)$，那么$C$君就在$(0,0)$位置上

考慮能被看到的小朋友的點坐標滿足的性質(zhì)

根據(jù)直線可以由向量刻畫，設$(x,y)$小朋友能被看到，那么這條直線上的$\lambda >1,(\lambda x,\lambda y)$都會被擋住

且$\gcd (\lambda x,\lambda y)=\lambda (x,y)\ge \lambda >1$

也就是說，如果$\gcd (x,y)>1$該小朋友會被擋住

如果$\gcd (x,y)=1$的小朋友會被擋住，那么一定存在$(\frac{x}{\mu },\frac{y}{\mu }),\mu >1$的小朋友存在，顯然不存在這樣的點

綜上，當且僅當小朋友的橫縱坐標互質(zhì)的時候，才會被看見

轉(zhuǎn)述成數(shù)學語言，即：$ans={\sum }_{i=0}^{n?1}{\sum }_{j=0}^{n?1}[\gcd (i,j)=1]$

$?{\sum }_{i=0}^{n?1}{\sum }_{j=0}^{i?1}[\gcd (i,j)=1]+{\sum }_{i=0}^{n?1}{\sum }_{j=i}^i[\gcd (i,j)=1]+{\sum }_{i=0}^{n?1}{\sum }_{j=i+1}^{n?1}[\gcd (i,j)=1]$

${\sum }_{i=0}^{n?1}{\sum }_{j=i}^i[\gcd (i,j)=1]$代表$y=x$直線，顯然只能看到一個小朋友，然后就可以刪去了

$n\times n$的圖，$C$君在原點處，隱藏的性質(zhì)是看到的小朋友關于$y=x$直線對稱

式子繼續(xù)化為$2\left({\sum }_{i=0}^{n?1}{\sum }_{j=0}^{i?1}\right[\gcd (i,j)=1\left]\right)$

驚奇的發(fā)現(xiàn)內(nèi)層循環(huán)的取值范圍以及要求完全符合歐拉函數(shù)$\phi$的定義

于是乎，最終答案成為$1+2{\sum }_{i=0}^{n?1}\phi (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;}elsephi[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

${\sum }_{i=1}^n\mathrm{lcm}(i,j)?{\sum }_{i=1}^n\frac{i\times n}{\gcd (i,n)}$

$\because \gcd (i,n)=\gcd (n?i,n)$，兩兩$\gcd$相同的合并$i+(n?i)=n$

$\frac{1}{2}({\sum }_{i=1}^{n?1}\frac{i?n}{\gcd (i,n)}+{\sum }_{i=n?1}^1\frac{i?n}{\gcd (i,n)})+\mathrm{lcm}(n,n)=n+\frac{1}{2}{\sum }_{i=1}^{n?1}\frac{n^2}{\gcd (i,j)}$

$\gcd (i,n)=d$的$i$的個數(shù)有$?(\frac{n}{d})$個$(gcd(\frac{i}{d},\frac{n}{d})=1$的個數(shù)有$?(\frac{n}{d}))$

$?n+\frac{1}{2}{\sum }_{i=1}^{n?1}\frac{n^2}{\gcd (i,j)}=n+\frac{1}{2}{\sum }_{d|n}\frac{n^2??(\frac{n}{d})}{d}=n+\frac{1}{2}{\sum }_{d|n}{n}^2?\frac{?(d)}{\frac{n}{d}}$

$=n+n{\sum }_{d|n}\frac{d??(d)}{2}$

線性篩預處理

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;}elsephi[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; }

總結(jié)

以上是生活随笔為你收集整理的[数论系列一]C Looooops，跳跳棋，The Luckiest number，CF906D Power Tower，Minimal Power of Prime，仪仗队，LCMSUM的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。