1. 題目列表
- POJ2635（高精度求模：同余模運算姨裸、Java大數(shù)）
- POJ3292（數(shù)篩 + 和的打表：樹狀數(shù)組）
- POJ1845（冪的因子和問題瑟押，質(zhì)因子分解+快速冪+等比數(shù)列遞歸求和+同余）
- POJ2115（求解ax + by = c線性方程的整數(shù)解：擴(kuò)展歐幾里得算法）
2. 數(shù)論中三個算法
2.1 擴(kuò)展歐幾里得算法
問題1：求 的所有整數(shù)解悠汽。
擴(kuò)展歐幾里得算法：當(dāng)計算時葵擎，有
成立探橱，而在計算
時资柔，有
成立甘桑。因此
成立拍皮，而
，則有
成立跑杭，對比等號左右邊有以下的遞推公式
遞歸邊界：當(dāng)
時铆帽，
即為
，
是
的一組解德谅。代碼模板如下：
int exGcd(int a, int b, int& x, int& y){
if (b == 0){ // 當(dāng) gcd(a, b) 當(dāng)b=0爹橱，返回a
x = 1;
y = 0;
return a;
}
int g = exGcd(b, a % b, x, y); // 遞歸求gcd
int temp = x; // 更新x和y
x = y;
y = temp - (a / b) * y;
return g;
}
在得到這樣的一組解之后，就可以通過下面的式子得到全部解：
也就是說愧驱，
和
的所有解分別以
與
為周期。此外组砚，上述方程的最小非負(fù)整數(shù)解為
問題2：求解方程的所有整數(shù)解艾帐。
方程存在解的充要條件是
，且一組解為
其中
和
是方程
的一組解盆偿。因此
的全部解的公式為
同樣事扭，
和
的所有解分別以
與
為周期。此外句旱，上述方程的最小非負(fù)整數(shù)解為
2.2 同于模運算
問題：求解同余式所有的解腥泥。
同余式的意義：若，則稱
為上述同余式的一個解啃匿。問題可轉(zhuǎn)化為：存在整數(shù)
使得
成立蛔外，即
成立。上式可以通過擴(kuò)展歐幾里得算法求解溯乒，于是我們可以得到以下的結(jié)論：
設(shè)
是整數(shù)夹厌，其中
，則
(1). 若裆悄，則同余方程式
無解矛纹。
(2). 若，則同余方程式
個模
意義夏不同的解光稼，且解的形式為
其中
,
是
的一個解或南。
2.3 同余模定理（大數(shù)求模）
來源https://blog.csdn.net/lyy289065406/article/details/6648530
當(dāng)123是一個大數(shù)時，就不能直接求艾君，只能通過同余模定理對大數(shù)“分塊”間接求模
具體做法是：
先求1%3 = 1
再求（1*10+2）%3 = 0
再求 （0*10+4）% 3 = 1
那么就間接得到124%3=1采够，這是顯然正確的
而且不難發(fā)現(xiàn)， （110+2）10+4 = 124
這是在10進(jìn)制下的做法冰垄，千進(jìn)制也同理蹬癌，*10改為*1000就可以了，下面是代碼模板：
/*高精度K對p求模，因數(shù)檢查(整除)*/
bool mod(const int* K,const int p,const int len)
{
int sq=0;
for(int i=len-1;i>=0;i--) //千進(jìn)制K是逆序存放
sq=(sq*1000+K[i])%p; //同余模定理
if(!sq) //K被整除
return false;
return true;
}
3. POJ1845——Sumdiv
3.1 題目描述
Description
Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).
Input
The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.
Output
The only line of the output will contain S modulo 9901.
Sample Input
2 3
Sample Output
15
Hint
2^3 = 8.
The natural divisors of 8 are: 1,2,4,8. Their sum is 15.
15 modulo 9901 is 15 (that should be output).
3.2 解決思路
(來自https://www.cnblogs.com/shenben/p/6264322.html)
本題的要點是：質(zhì)因子分解 + 快速冪 + 等比數(shù)列遞歸求和 + 同余逝薪，重點理解代碼中各要點的實現(xiàn)伴奥。
注意：在容易超出int范圍的題目，數(shù)據(jù)類型最好設(shè)置為long long 或_int64
3.3 代碼
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
/*
題意：
求A^{B}的所有因子和翼闽，結(jié)果MOD 9901
思路：
快速冪 + 冪的因子和(質(zhì)因子分解) + 等比數(shù)列求和
注意：直接將快速mod冪的結(jié)果拿出來求因子和是錯的拾徙，因為不滿足同余
*/
const int MOD = 9901;
const int maxPrime = 1000;
struct Factor{
ll f, num;
}factors[maxPrime];
ll quickPow(ll a, ll b){
ll res = 1;
while (b){
if (b % 2)
res = (res * a) % MOD;
a = (a * a) % MOD;
b /= 2;
}
return res;
}
int findFactors(ll a){
int index = 0;
// 奇偶法尋找質(zhì)因子
for (int i = 2; i * i <= a; ){
if (a % i == 0){
factors[index].f = i;
factors[index].num = 0;
while (a % i == 0){
factors[index].num ++;
a /= i;
}
index ++;
}
if (i == 2)
i++;
else i += 2;
}
if (a != 1){ // 如果A本身是素數(shù)
factors[index].f = a;
factors[index++].num = 1;
}
return index;
}
ll multipleSum(ll p, ll n){ // 二分遞歸求等比數(shù)列的和 sum=1+p+p^2+...+p^n
if (n == 0){
return 1;
}
if (n % 2){
return ((1 + quickPow(p, n / 2 + 1)) * multipleSum(p, n / 2)) % MOD;
}else{
return ((1 + quickPow(p, n / 2 + 1)) * multipleSum(p, n / 2 - 1) + quickPow(p, n / 2)) % MOD;
}
}
int main(){
ll a, b;
// while (~scanf("%lld%lld", &a, &b)){
scanf("%lld%lld", &a, &b);
int len = findFactors(a); // 找到a的factors
int sum = 1;
for (int i = 0; i < len; i++){
// 注意：這里的factors[i].num * b 可能超出int，因此全部設(shè)為ll
sum = (sum * (multipleSum(factors[i].f, factors[i].num * b)) % MOD) % MOD;
}
printf("%lld\n", sum);
// }
return 0;
}
4. POJ2635——The Embarrassed Cryptographer
4.1 題目描述
Description
The young and very promising cryptographer Odd Even has implemented the security module of a large system with thousands of users, which is now in use in his company. The cryptographic keys are created from the product of two primes, and are believed to be secure because there is no known method for factoring such a product effectively.
What Odd Even did not think of, was that both factors in a key should be large, not just their product. It is now possible that some of the users of the system have weak keys. In a desperate attempt not to be fired, Odd Even secretly goes through all the users keys, to check if they are strong enough. He uses his very poweful Atari, and is especially careful when checking his boss' key.
Input
The input consists of no more than 20 test cases. Each test case is a line with the integers 4 <= K <= 10100 and 2 <= L <= 106. K is the key itself, a product of two primes. L is the wanted minimum size of the factors in the key. The input set is terminated by a case where K = 0 and L = 0.
Output
For each number K, if one of its factors are strictly less than the required L, your program should output "BAD p", where p is the smallest factor in K. Otherwise, it should output "GOOD". Cases should be separated by a line-break.
Sample Input
143 10
143 20
667 20
667 30
2573 30
2573 40
0 0
Sample Output
GOOD
BAD 11
GOOD
BAD 23
GOOD
BAD 31
4.2 解決思路
題意：對于大素數(shù)k=p*q感局，給定數(shù)L尼啡，判斷K是否有小于L的質(zhì)因子，如果有询微，則輸出bad p崖瞭，其中p是較小的一個質(zhì)因子，否則撑毛，輸出good 书聚。
Java大數(shù)呈上。
4.3 代碼
package 數(shù)學(xué);
import java.io.BufferedInputStream;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class POJ2635 {
/*
* 題意：對于大素數(shù)k=p*q藻雌，給定數(shù)L雌续，判斷K是否有L的質(zhì)因子，如果有胯杭，則輸出bad p驯杜，其中
* p是較小的一個質(zhì)因子，否則做个，輸出good鸽心。
* 思路：素數(shù)打表+大數(shù)整除，大數(shù)整除可使用同余模定理居暖，但使用java大數(shù)顽频，也能過
*
*/
public static void main(String[] args){
Scanner sc = new Scanner(new BufferedInputStream(System.in));
while (true){
BigInteger K = sc.nextBigInteger();
int L = sc.nextInt();
if (K.equals(BigInteger.ZERO) && L == 0) break;
List<Integer> primes = findPrime(L);
boolean flag = false;
int res = 0;
for (int prime : primes){
// System.out.println("prime:" + prime);
if (K.mod(new BigInteger(String.valueOf(prime))).equals(BigInteger.ZERO)){
flag = true;
res = prime;
break;
}
}
if (flag) System.out.println("BAD " + res);
else System.out.println("GOOD");
}
}
public static List<Integer> findPrime(int L){
boolean[] prime = new boolean[L + 1];
Arrays.fill(prime, true);
// 素數(shù)篩
List<Integer> list = new ArrayList<Integer>();
for (int i = 2; i < L; i++){
if (prime[i]){
// 如果i是素數(shù)，則其倍數(shù)不是
for (int j = i + i; j < L; j += i)
prime[j] = false;
list.add(i);
}
}
return list;
}
}
5. POJ3292—Semi-prime H-numbers
5.1 題目描述
Description
This problem is based on an exercise of David Hilbert, who pedagogically suggested that one study the theory of 4n+1 numbers. Here, we do only a bit of that.
An H-number is a positive number which is one more than a multiple of four: 1, 5, 9, 13, 17, 21,... are the H-numbers. For this problem we pretend that these are the only numbers. The H-numbers are closed under multiplication.
As with regular integers, we partition the H-numbers into units, H-primes, and H-composites. 1 is the only unit. An H-number h is H-prime if it is not the unit, and is the product of two H-numbers in only one way: 1 × h. The rest of the numbers are H-composite.
For examples, the first few H-composites are: 5 × 5 = 25, 5 × 9 = 45, 5 × 13 = 65, 9 × 9 = 81, 5 × 17 = 85.
Your task is to count the number of H-semi-primes. An H-semi-prime is an H-number which is the product of exactly two H-primes. The two H-primes may be equal or different. In the example above, all five numbers are H-semi-primes. 125 = 5 × 5 × 5 is not an H-semi-prime, because it's the product of three H-primes.
Input
Each line of input contains an H-number ≤ 1,000,001. The last line of input contains 0 and this line should not be processed.
Output
For each inputted H-number h, print a line stating h and the number of H-semi-primes between 1 and h inclusive, separated by one space in the format shown in the sample.
Sample Input
21
85
789
0
Sample Output
21 0
85 5
789 62
5.2 解決思路
定義:
H-Number = 4n+1, n=0,1,2,...
H-Primes = p*q,其中p和q分別是H-Number中的素數(shù)太闺。
問題：求1~h的所有符合條件的H-Primes的個數(shù)糯景，h<=1000,001。
思路：
數(shù)篩 + 結(jié)果打表(樹狀數(shù)組求1~n的和)跟束，注意：當(dāng)一個問題
的所有測試用例都能在一次性求出時莺奸，則一次性求出丑孩。
5.3 代碼
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define lowbit(x) ((x) & (-x))
using namespace std;
/*
定義:
H-Number = 4n+1, n=0,1,2,...
H-Primes = p*q,其中p和q分別是H-Number中的素數(shù)冀宴。
問題：求1~h的所有符合條件的H-Primes的個數(shù)，h<=1000,001温学。
思路：
素數(shù)篩 + 結(jié)果打表(樹狀數(shù)組求1~n的和)略贮，注意當(dāng)一個問題
的所有測試用例都能在一次性求出時，則一次性求出。
*/
vector<int> primes;
const int maxn = 1000001;
bool isPrime[maxn + 10];
bool visited[maxn + 10];
int c[maxn]; // 樹狀數(shù)組適合求動態(tài)更新的前i項和
int getSum(int x){
// 獲取前x的sum和
int sum = 0;
for (int i = x; i >= 1; i -= lowbit(i))
sum += c[i];
return sum;
}
void update(int v, int x){
for (int i = v; i <= maxn; i += lowbit(i))
c[i] += x;
}
void findPrimes(){
for (int i = 5; i <= maxn; i += 4){
if (isPrime[i]){
for (int j = i + i; j <= maxn; j += i)
isPrime[j] = false;
primes.push_back(i);
for (int j = 0; j < primes.size(); j++){
if (maxn / i >= primes[j]){
if (!visited[i * primes[j]]){
visited[i * primes[j]] = true;
update(i * primes[j], 1); // 樹狀數(shù)組更新
}
}else{
break;
}
}
}
}
}
int main(){
int n;
primes.clear();
memset(isPrime, true, sizeof(isPrime));
memset(visited, false, sizeof(visited));
memset(c, 0, sizeof(c));
findPrimes(); // 求出所有的H-semi-number個數(shù)
while (~scanf("%d", &n) && n){
printf("%d %d\n", n, getSum(n));
}
return 0;
}
6. POJ2115——C Looooops
6.1 題目描述
Description
A Compiler Mystery: We are given a C-language style for loop of type
for (variable = A; variable != B; variable += C)
statement;
I.e., a loop which starts by setting variable to value A and while variable is not equal to B, repeats statement followed by increasing the variable by C. We want to know how many times does the statement get executed for particular values of A, B and C, assuming that all arithmetics is calculated in a k-bit unsigned integer type (with values 0 <= x < 2k) modulo 2k.
Input
The input consists of several instances. Each instance is described by a single line with four integers A, B, C, k separated by a single space. The integer k (1 <= k <= 32) is the number of bits of the control variable of the loop and A, B, C (0 <= A, B, C < 2k) are the parameters of the loop.
The input is finished by a line containing four zeros.
Output
The output consists of several lines corresponding to the instances on the input. The i-th line contains either the number of executions of the statement in the i-th instance (a single integer number) or the word FOREVER if the loop does not terminate.
Sample Input
3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0
Sample Output
0
2
32766
FOREVER
6.2 解決思路
問題轉(zhuǎn)化為：求逃延，是否存在整數(shù)解
览妖，問題轉(zhuǎn)換為求解方程
，移項得到
揽祥，因此問題就轉(zhuǎn)換為求解上述方程的整數(shù)解讽膏，若無解輸出"FOREVER"，若有解拄丰，輸出最小非負(fù)整數(shù)解
府树，使用擴(kuò)展歐幾里得算法易求解。
6.3 代碼
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
ll exGcd(ll a, ll b, ll& x, ll& y){
if (b == 0){ // 當(dāng) gcd(a, b) 當(dāng)b=0料按，返回a
x = 1;
y = 0;
return a;
}
ll g = exGcd(b, a % b, x, y); // 遞歸求gcd
ll temp = x; // 更新x和y
x = y;
y = temp - (a / b) * y;
return g;
}
int main(){
ll k, A, B, C;
while (~scanf("%lld%lld%lld%lld", &A, &B, &C, &k)){
if (!A && !B && !C && !k) break;
// Cx - 2^k * y = B - A問題轉(zhuǎn)換求解ax + by = c最小的非負(fù)整數(shù)x
ll a = C, b = (ll)1<<k, c = B - A; // 1注意左移之前強(qiáng)轉(zhuǎn)位64位奄侠，否則32位時，會溢出
ll x0, y0;
ll gcd = exGcd(a, b, x0, y0); // 求 ax + by = gcd的初始解
if (c % gcd != 0){ // ax + by = c 無整數(shù)解
printf("FOREVER\n");
continue;
}
ll x = c * x0 / gcd; // 求ax + by = c的一個解
printf("%lld\n", (x % (b / gcd) + b / gcd) % (b / gcd)); // 求ax + by = c的最小非負(fù)整數(shù)解
}
return 0;
}
