數論複習

01-24

2017.11.28

今天看了一天的初等數論。

先上了一道比（fei）較（chang）水的題目。

HDU-2136

求一個數的最大質因數在所有質數中的排名。

數據範圍是 $1000000$ .

開始覺得可以在線求解然後就T掉了。

加上記憶化…… 還是T掉了。

粗略估計了一下，其實這樣的在線的計算量是很恐怖的。

$1000000$ 以內有 $78498$ 個質數。

對於一個數可以拆成一個很小的質數 $imes$ 的次方，那麼我就要從 $78498$ 倒序遍歷到那個質數的 $rank$ 才可以返回答案，這樣的計算量單單在 $1000000$ 個不同數的詢問都無法接受的。

複雜度大概是 $O(2的次冪的數的個數 imes78498+3的次冪的數的個數 imes78497......) = O( n sqrt{n} )$

呃，一共是 $1010130043$ 次。

於是決定直接離線做...

考慮到 $x$ 的每一個 $prime-factor$ 都可能會對 $ans[x]$ 產生貢獻。

那麼我們直接對每一個 $prim- factor$ 順序枚舉，設為 $p$ ，把 $p$ 有可能產生貢獻的數的 $ans$ 全部設為 $p$ 。這樣做下去，那麼數 $x$ 一定被它最大的質因數最後更新。

複雜度？

相當於一般的素數篩法——埃氏篩法， $O(nlog(logn))$ 。

實際是 $2775210$ 次

對於簡單題其實也可以細究並且仔細考慮的。

其實可以打表的……

先寫線性篩再求答案其實比較愚蠢，可以直接求答案，像埃氏篩法一樣。

# include <cstdio>bool ispr [1000005] ;int ans [1000005], primes [1000005], ptot ;void Liner_Shaker ( int N ) { for ( register int i = 2 ; i <= N ; ++ i ) ispr [i] = 1 ; for ( register int i = 2 ; i <= N ; ++ i ) { if ( ispr [i] ) { primes [ans [i] = ++ ptot] = i ; } for ( register int j = 1, to ; j <= ptot && ( to = primes [j] * i ) <= N ; ++ j ) { ispr [to] = 0 ; if ( i % primes [j] == 0 ) break ; } } for ( int i = 1 ; i <= ptot ; ++ i ) for ( int j = 2, to ; ( to = j * primes [i] ) <= N ; ++ j ) { ans [to] = i ; }}inline int MaxPrimeFactor ( int x ) { return ans [x] ;}int main ( ) { Liner_Shaker ( 1000000 ) ; int n ; while ( ~ scanf ( "%d", & n ) ) { printf ( "%d ", MaxPrimeFactor ( n ) ) ; }}

經過Doggu神犇的指點，這道題可以 $O(n)$ 的時間解決。但實際效果和 $O(log(logn))$ 差不多。

我們可以在線性篩直接預處理出每個數 $x$ 的最小質因數 $minp[x]$ 和最大質因數 $maxp[x]$ 。

首先對於一個質數 $p$ ，

$maxp [p] = minp [p] = p$

對於其他的任意一個數：

$minp [i * primes[j]] = primes [j]$

$maxp [i * primes [j]] = maxp [i]$

我已經ZZ到把這個忘了，對於這道題，直接存下標就可以了。

# include <cstdio>bool ispr [1000005] ;int maxp [1000005], primes [1000005], ptot ;void Liner_Shaker ( int N ) { for ( register int i = 2 ; i <= N ; ++ i ) ispr [i] = 1 ; for ( register int i = 2 ; i <= N ; ++ i ) { if ( ispr [i] ) { primes [maxp [i] = ++ ptot] = i ; } for ( register int j = 1, to ; j <= ptot && ( to = primes [j] * i ) <= N ; ++ j ) { ispr [to] = 0 ; maxp [to] = maxp [i] ; if ( i % primes [j] == 0 ) break ; } }}inline int MaxPrimeFactor ( int x ) { return maxp [x] ;}int main ( ) { Liner_Shaker ( 1000000 ) ; int n ; while ( ~ scanf ( "%d", & n ) ) { printf ( "%d ", MaxPrimeFactor ( n ) ) ; }}

然後還是一道比較水的題

BZOJ2296

給一個數 $a$ ，構造出一個數 $x$ ，使得 $x$ 包含 $0$ 到 $9$ 所有的數字，並且 $x$ $mod$ $a=0$ 。無解輸出 $-1$ 。 $0 leq a leq 1000000$ , $0 leq x leq 1e16$ 。

考慮到需要包含 $0$ 到 $9$ 所有的數字，我們可以先構造一個數字 $lambda$ 使得 $lambda$ 已經滿足要求，然後再在 $lambda$ 的基礎上添加數字，使得滿足 $lambda$ $mod$ $a=0$ 。

如何添加，假設當前的 $lambda$ $mod$ $x$ $=r$ ,那麼我的 $lambda+x - r$ 一定滿足要求。且 $(x - r)leq1000000$ ，那麼只要我的 $lambda$ 最後的 $7$ 位都是0，就對第一個條件沒有影響了。

可是這樣的話最後的結果會大於 $1e16$ 吖。

所以 $lambda$ 取為 $9876543210 imes1000000$ （或者是 $aaaaaaaaa0 imes1000000$ 這樣的數字）是最好的，最極端的 $x$ 取到 $1000000$ 答案會是 $9876543211000000$ ，不會錯誤，而對於 $1023456789000000$ ， $x$ 取到 $1000000$ 答案會是 $1023456790000000$ 就會失掉一個數字。

/************************************************************** Problem: 2296 User: Lazer2001 Language: C++ Result: Accepted Time:0 ms Memory:820 kb****************************************************************/ # include <cstdio># include <cassert> int main ( ) { const long long base = 1236857490 * 1000000LL ; int T ; scanf ( "%d", & T ) ; while ( T -- ) { long long x ; scanf ( "%lld", & x ) ; printf ( "%lld ", x == 0 ? -1LL : base + ( x - base % x ) ) ; }}

2017.11.29

然後還是一個很ZZ的題，本來20mins切掉的搞了近一個小時。

因為我的CRT裡面求出來有負數……

BZOJ-1951

一句話題意：

求 $g^{Sigma_{d|n}^{n}C_{n}^{d}} mod$ $999911659$

其中 $0 leq g, n leq 1e9$

大水題……

歐拉定理

$a ^{varphi(m)} equiv1;mod; mquad gcd(a,m)=1$

所以 $a ^ {x}$ 的循環節為 $varphi(x)$ ，

則 $a^{x}equiv a ^{x,mod,varphi(m)} mod; mquad gcd(a,m)=1$ （自己證明或者百度，比較簡單）

還有它的推廣， $a^{x}equiv a ^{x,mod,varphi(m)+varphi(m)} mod; m$ （這個證明比較繁瑣見這裡）

由歐拉定理

轉化為當 $gcd(g,p)=1$ 時 $g^{Sigma_{d|n}^{n}C_{n}^{d},mod,varphi(p)} mod,p$

$gcd(g,p)=0$ 時，答案為 $0$ .

當然可以一起處理用歐拉定理的推廣

$g^{Sigma_{d|n}^{n}C_{n}^{d},mod,varphi(p)+varphi(p)} mod,p$ 直接合併處理。

對於題目中的 $p=999911659$ 是一個質數

故 $varphi(p)=p-1=999911658$

這個數不是質數，分解質因數 $999911658=2 imes3 imes4679 imes35617$ 。

我們發現每一個質因數的次冪都是 $1$ ，所以直接分成每一個質因數用 $Lucas$ 定理處理組合數然後得到四個同餘式用中國剩餘定理合併起來，最後得到指數用快速冪計算。

否則就要用拓展 $Lucas$ 定理。

$Lucas$ 定理和中國剩餘定理什麼的就不展開說了。

/************************************************************** Problem: 1951 User: Lazer2001 Language: C++ Result: Accepted Time:184 ms Memory:2792 kb****************************************************************/ # include <bits/stdc++.h> class CRT { private : int a [5], m [5] ; inline void exgcd ( int a, int b, int& x, int& y ) { if ( ! b ) { x = 1, y = 0 ; return ; } exgcd ( b, a % b, y, x ) ; y -= a / b * x ; } public : CRT ( ) { } CRT ( int* a, int* m ) { for ( int i = 0 ; i < 4 ; ++ i ) this -> a [i] = a [i], this -> m [i] = m [i] ; } inline long long main ( ) { int N ( 1 ), rt ( 0 ) ; for ( int i = 0 ; i < 4 ; ++ i ) N *= m [i] ; for ( int i = 0 ; i < 4 ; ++ i ) { int t = N / m [i] ; int x, y ; exgcd ( t, m [i], x, y ) ; rt += 1LL * t * x % N * 1LL * a [i] % N ; while ( rt < 0 ) rt += N ; while ( rt >= N ) rt -= N ; } return rt ; }} Crt ; # define N 100010# define RG register class Solution { private : int Mod ; int inv [N], fac [N] ; inline int Lucas ( int n, int m ) { if ( m > n ) return 0 ; if ( n < Mod ) return 1LL * fac [n] * inv [m] % Mod * 1LL * inv [n - m] % Mod ; return 1LL * Lucas ( n / Mod, m / Mod ) * Lucas ( n % Mod, m % Mod ) % Mod ; } public : Solution ( ) { } Solution ( const int& Mod ) : Mod ( Mod ) { inv [0] = inv [1] = 1, fac [0] = fac [1] = 1 ; // fac [0]!!! for ( RG int i = 2 ; i < Mod ; ++ i ) fac [i] = 1LL * i * fac [i - 1] % Mod ; for ( RG int i = 2 ; i < Mod ; ++ i ) inv [i] = 1LL * ( Mod - Mod / i ) * inv [Mod % i] % Mod ; for ( RG int i = 2 ; i < Mod ; ++ i ) inv [i] = 1LL * inv [i] * inv [i - 1] % Mod ; } inline int main ( int n ) { int ans ( 0 ) ; for ( RG int i = 1, l = sqrt ( n + 0.5 ), tmp ; i <= l ; ++ i ) if ( n % i == 0 ) { tmp = n / i ; if ( tmp != i ) ans += Lucas ( n, tmp ) ; ans += Lucas ( n, i ) ; while ( ans >= Mod ) ans -= Mod ; } return ans ; }} Sol ; inline int mpow ( register int a, register int x, const int& Mod, register int rt = 1 ) { while ( x ) { if ( x & 1 ) rt = 1LL * rt * a % Mod ; a = 1LL * a * a % Mod ; x >>= 1 ; } return rt ;} # undef N# undef RG int mod [] = { 2,3,4679,35617 } ;int ans [4] ; int main ( ) {// freopen ( "in.txt", "r", stdin ) ; int g, n ; scanf ( "%d%d", & n, & g ) ; if ( ( g %= 999911659 ) == 0 ) return puts ( "0" ), 0 ; for ( int i = 0 ; i < 4 ; ++ i ) { Sol = Solution ( mod [i] ) ; ans [i] = Sol.main ( n ) ; } Crt = CRT ( ans, mod ) ; printf ( "%d ", mpow ( g, Crt.main ( ), 999911659 ) ) ;}

乘法原理水題

BZOJ-2751

題意：

已知 $m$ 個位置，每個位置可以放 $[1,n]$ 中的數，有 $k$ 個限制條件 $(pos,x)$ 表示 $pos$ 位置上不能放數 $x$ 。

定義一個數列的積為數列中各個元素的乘積，求所有可能數列的積之和。

結果對 $1e9+7$ 取模。

其中 $0leq n,m leq 1e9, 0leq kleq100000$ .

我們先考慮沒有限制條件，即 $k=0$ 的情況。

每個位置都可以取遍 $[1,n]$ 中的數，我們來推導這種情況的結果（雖然顯然）。

用 $a_i$ 來表示 $i$ 位置的取值

$a_1 = 1,a_2=1,a_3=1,......,a_m=1$ 結果為 $1 imes1 imes1 imes...... imes1$

$a_1 = 1,a_2=1,a_3=1,......,a_m=2$ 結果為 $1 imes1 imes1 imes...... imes2$

$a_1 = 1,a_2=1,a_3=1,......,a_m=3$ 結果為 $1 imes1 imes1 imes...... imes3$

$......$

$a_1 = 1,a_2=1,a_3=1,......,a_m=n$ 結果為 $1 imes1 imes1 imes...... imes,n$

$......$

對於每一個位置變化的答案為 $Sigma_{1}^{n}=frac{n imes(n+1)}{2}$

那麼答案為 $（frac{n imes(n+1)}{2}）^m$

回到原題，

所以對於無限制的位置，設有 $x$ 個，答案是 $（frac{n imes(n+1)}{2}）^x$

設 $p$ 個位置有限制，對於有限制的位置 $l_i$ ，暴力計算每個位置的貢獻 $w_i$ 。

然後根據乘法原理乘起來。

$ans=$ $（frac{n imes(n+1)}{2}）^{m-p} imesprod_{i=1}^{p}w_i$

雖然可以一次 $sort$ 維護不同.但是我還是想寫 $map+set$ .

/************************************************************** Problem: 2751 User: Lazer2001 Language: C++ Result: Accepted Time:376 ms Memory:6972 kb****************************************************************/ # include <bits/stdc++.h> inline int read ( ) { register int x, c ; while ( isspace ( c = getchar ( ) ) ) ; for ( x = -48 + c ; isdigit ( c = getchar ( ) ) ; ( x *= 10 ) += c - 48 ) ; return x ;} # define N 100010 std :: map < int, std :: set < int > > S ; # undef N # define Mod 1000000007 inline int mpow ( register int a, register int x, register int rt = 1 ) { for ( ; x ; x >>= 1, a = 1LL * a * a % Mod ) if ( x & 1 ) { rt = 1LL * rt * a % Mod ; } return rt ;} int main ( ) { int n ( read ( ) ), m ( read ( ) ), k ( read ( ) ) ; while ( k -- ) { int pos ( read ( ) ), v ( read ( ) ) ; S [pos].insert ( v ) ; } int remain_pos = m ; int rt = 1 ; const int sum = 1LL * n * ( n + 1 ) % Mod * ( ( Mod + 1 ) >> 1 ) % Mod ; // ( Mod + 1 ) >> 1 = inv (2) for ( std :: map < int, std :: set < int > > :: iterator it0 = S.begin ( ) ; it0 != S.end ( ) ; ++ it0 ) { -- remain_pos ; int tmp = sum ; for ( std :: set < int > :: iterator it1 = ( it0 -> second ).begin ( ) ; it1 != ( it0 -> second ).end ( ) ; ++ it1 ) tmp -= *it1 ; rt = 1LL * rt * tmp % Mod ; while ( rt < 0 ) rt += Mod ; // alternative !!! } printf ( "%d ", 1LL * rt * mpow ( sum, remain_pos ) % Mod ) ; return 0 ;} # undef Mod