目录
51Nod – 1119 机器人走方格 V2 （费马小定理）
HDU 6025 Coprime Sequence（前缀GCD+后缀GCD）
CodeForces – 678D Iterated Linear Function（快速幂）
POJ 2262 Goldbach’s Conjecture （素数筛选）
POJ 2478 Farey Sequence （欧拉定理）
HDU 3037 Saving Beans (Lucas定理)
51Nod – 1119 机器人走方格 V2 （费马小定理）
题解：:本题主要考察了费马小定理，但是要用到排列组合，机器人只能往右走m-1步和向下走n-1步，所以机器人一共要走m+n-2步，能有多少种走法就是在于什么时候向下走，或者什么时候向右走，所以多少种走法就是，在m+n-2里面选m-1,或者n-1，这两个是相等的所以求任意一个就行了，后面就是费马小定理和快速幂就能够做了。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
const int maxn = 1000000;
const int mod = 1e9 + 7;
#define me(a) memset(a,0,sizeof(a))
#define ll long long
using namespace std;
ll qpow(ll a, ll b) {
ll res = 1;
a = a % mod;
while (b) {
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int gcd(int a, int b) {
if (!b)
return a;
else
return gcd(a, a % b);
}
int main() {
ll m, n;
cin >> m >> n;
ll a = m + n - 2;
ll b = min(m - 1, n - 1);
ll a1 = 1, b1 = 1;
for (int i = a; i >= a - b + 1; i--)
a1 = a1 * i % mod;
for (int i = b; i > 0; i--)
b1 = b1 * i % mod;
cout << a1 % mod * qpow(b1, mod - 2) % mod << endl;
return 0;
}
///(a/b)%mod=a%mod*b^(mod-2)%mod
HDU 2710 Max Factor （素数筛选）
题解：先拿数筛跑一遍然后再找，需要注意的是这题是多组输入，但是题上没有告诉。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
const int maxn = 2e4 + 100;
const int mod = 10000;
#define me(a) memset(a,0,sizeof(a))
#define ll long long
using namespace std;
bool vis[maxn];
int s[maxn], l = 0;
void ss() {
me(vis);
for (int i = 2; i < maxn; i++) {
if (!vis[i]) {
s[l++] = i;
for (int j = i + i; j < maxn; j += i)
vis[j] = 1;
}
}
}
int main() {
ss();
int n, a[maxn];
while (cin >> n) {
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
int x = 0, temp = 0;
for (int i = 0; i < n; i++)
for (int j = 0; s[j] <= a[i] && j < l; j++)
if (a[i] % s[j] == 0 && s[j] > temp) {
x = i;
temp = s[j];
}
cout << a[x] << endl;
}
return 0;
}
POJ2142 The Balance （扩展欧几里得）
题解：一看就是解一个方程，肯定是要用扩展欧几里得，但是要求使x+y的最小两个正整数，所以每次只能先求出x的最小正数值，再根据方程求出y，另一种是根据y，求出x的值。两者比较，取小的输出。
/*思路：是扩展欧几里得的应用。 设ax + by = 1,求出x和y的值，因为我们要求ax + by = n的解，所以需要将x y的值乘以n 。因为题目中要求x和y的值都要为正，然而，易知，ax + by = 1在a和b都为正数的情况下，x 和 y必有一个数是负的。 因此我们需要把x 和 y的值转化为合法的正值。 我们先把x转化为正值，易知，把x转化为正值的方式是 x = (x % a + a) % a，这样x就成为最小的正值， 我们再根据所求出的x的最小正值求出y的值，则 y = (n – a * x) / b，若求出的y为负值， 则把y变正，意思就是砝码放置的位置有左右之分，可以左面的减去右面的，也可以右面的减去左面的。 同理，再求出y为最小合法正值时x的解，将这两种情况比较取小的即可。*/
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
#define me(a, b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
#define mid (l+r)/2
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
typedef long long ll;
using namespace std;
int ex_gcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = ex_gcd(b, a % b, x, y);
int temp = x;
x = y;
y = temp - a / b * y;
return d;
}
int main() {
int a, b, d, x, y;
while (scanf("%d%d%d", &a, &b, &d) && a + b + d) {
int md = ex_gcd(a, b, x, y);
a /= md, b /= md, d /= md;
int x1 = x * d;
x1 = (x1 % b + b) % b;///求满足条件的最小正值。
int y1 = (d - x1 * a) / b;
y1 = abs(y1);
int y2 = y * d;
y2 = (y2 % a + a) % a;
int x2 = (d - y2 * b) / a;
x2 = abs(x2);
if (x1 + y1 < x2 + y2)
printf("%d %d\n", x1, y1);
else
printf("%d %d\n", x2, y2);
}
return 0;
}
POJ 1061 青蛙的约会（扩展欧几里得）
题解：根据题意可立出方程x+m*i=y+n+k*L，整理得（n-m）*i+k*L=x-y；（青蛙跳了i步，绕了k圈）这就是一个欧几里得的题了。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 1e8;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
ll a, b, m, n, l, x, y;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int gcd = exgcd(b, a % b, x, y);
int temp = x;
x = y;
y = temp - a / b * y;
return gcd;
}
int main() {
while (cin >> a >> b >> m >> n >> l) {
ll x1 = n - m, c = a - b;
ll gcd = exgcd(x1, l, x, y);
if (c % gcd != 0)
cout << "Impossible" << endl;
else
cout << (x * (c / gcd) % l + l) % l << endl;
}
return 0;
}
洛谷 P1069 细胞分裂（质数分解）
题解：这个题不难，但是很考思想，首先是判断细胞数量能不能通过繁殖达到试管数量的整数倍。这个就需要质数分解了，首先是试管数量的分解，直接分解底数，再将每个底数的数目乘以指数就行了。（比如，12可以分为，2个2，一个3，那么12^2分解就有4个2,2个3，这个可以自己验证一下。），分解过后其实就比较简单了，只要查看细胞的数量分解质因子过后，是否包含试管数量分解过后的质因子。若包含，则可以通过繁殖达到试管数量的整数倍，反之则不行。然后在同一个细胞数量中选出质因子数相差最多，这也就是倍数最大的数，这样保证细胞繁殖这么多次一定能够达到试管的整数倍（要向上取整）。最后在每个细胞的最多繁殖数目中选出最小的，就是答案，细节看代码。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn = 1e4 + 5;
const int mod = 1e9;
const int inf = 1e9;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int ss[maxn << 2], l;
bool vis[maxn << 2];
map<int, int> q;
map<int, int> s;
void inct() {
l = 0;
for (int i = 2; i <= maxn * 3; i++)
if (!vis[i]) {
ss[l++] = i;
for (int j = i; j <= maxn * 3; j += i)
vis[j] = 1;
}
}
int main() {
int n, a[maxn], m1, m2;
inct();///素数筛选
cin >> n >> m1 >> m2;
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
for (int i = 0; i < l; i++) {
if (m1 == 1)
break;
while (m1 % ss[i] == 0)///分解质因子
{
m1 /= ss[i];
q[ss[i]]++;
}
if (q[ss[i]])
q[ss[i]] *= m2;///试管的每个质因子总数，需要乘以他的指数。
}
int k = inf, temp;
for (int i = 0; i < n; i++) {
s.clear(), temp = 0;
for (map<int, int>::iterator it = q.begin(); it != q.end(); it++) {
while (q[it->first] && a[i] % it->first == 0) {
a[i] /= it->first;
s[it->first]++;
}
if (q[it->first] && !s[it->first])///里面没有试管数量的质因子，怎么繁殖也不可能整除直接跳出
{
temp = inf;
break;
}
if (q[it->first] && q[it->first] > s[it->first]) {
int t1 = q[it->first] / s[it->first];///判断至少繁殖几次
q[it->first] % s[it->first] == 0 ? t1 : t1++;///向上取整
temp = max(t1, temp);
}
}
k = min(k, temp);
}
if (k == inf)
cout << "-1" << endl;
else
cout << k << endl;
return 0;
}
HDU2866 Special Prime （数论）
题解：推荐一篇博客
传送门
。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<vector>
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
#define me(a) memset(a,0,sizeof(a))
typedef long long ll;
using namespace std;
bool vis[maxn];
void prime() {
for (int i = 2; i < maxn; i++) {
if (!vis[i])
for (int j = i + i; j < maxn; j += i)
vis[j] = 1;
}
}
int main() {
int n;
prime();
while (~scanf("%d", &n)) {
int sum = 0;
for (int i = 1; 3 * i * i + 3 * i + 1 <= n; i++) {
int s = 3 * i * i + 3 * i + 1;
if (!vis[s])
sum++;
}
if (sum)
cout << sum << endl;
else
cout << "No Special Prime!" << endl;
}
return 0;
}
HDU 1573 X问题(中国剩余定理非互质情况)
题解：中国剩余定理不互质的情况，可以去网上找找写的好的博客看看，下面这张图就是中心思想。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<vector>
const int maxn = 1e2 + 5;
const int mod = 1e9 + 7;
#define me(a) memset(a,0,sizeof(a))
typedef long long ll;
using namespace std;
ll n, m, a[maxn], b[maxn], x, y;
int flog;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1, y = 0;
return a;
}
ll gcd = exgcd(b, a % b, x, y);
int temp = x;
x = y;
y = temp - a / b * y;
return gcd;
}
void CRT() {
int a1 = a[0], b1 = b[0];
for (int i = 1; i < m; i++) {
if (flog) continue;
ll a2 = a[i], b2 = b[i], c = b2 - b1;
int d = exgcd(a1, a2, x, y);
if (c % d) {
flog = 1;
continue;
}
int t = a2 / d;
x = (x * c / d % t + t) % t;
b1 += a1 * x, a1 *= a2 / d;///更新解
}
if (b1 > n || flog)
cout << "0" << endl;
else {
ll ans = (n - b1) / a1 + 1;///a1为最小公倍数，a1*i+b1都满足，b1是最小满足情况的
if (b1 == 0)
ans--;
cout << ans << endl;
}
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> n >> m;
for (int i = 0; i < m; i++)
cin >> a[i];
for (int i = 0; i < m; i++)
cin >> b[i];
flog = 0;
CRT();
}
return 0;
}
HDU 6025 Coprime Sequence（前缀GCD+后缀GCD）
题意：去掉一个数是剩下的GCD最大。
题解：这里使用两个数组，一个前缀GCD数组和一个后缀GCD数组，遍历一遍就好了。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 1e8;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int a[maxn], l[maxn], r[maxn];
int main() {
int t;
cin >> t;
while (t--) {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
l[1] = a[1], r[n] = a[n];
for (int i = 2; i <= n; i++)
l[i] = gcd(l[i - 1], a[i]);///保存前i项的GCD
for (int i = n - 1; i > 0; i--)
r[i] = gcd(r[i + 1], a[i]);///保存后i项的GCD
int ans = max(l[n - 1], r[2]);///因为数组是1到n，并且下面有i-1和i+1所以不能是max(l[n],r[1]);
for (int i = 2; i < n; i++)
ans = max(ans, gcd(l[i - 1], r[i + 1]));///gcd(l[i-1],r[i+1])就表示除开第i项后数列的GCD、
cout << ans << endl;
}
return 0;
}
HDU 5512 Pagodas（容斥）
题意：有1到n那么多座塔，但是只有a，b站着，有两个和尚在修塔，每次修塔只能在立着的两座塔选择做为，j，k。
题解：每次只能选择j+k或者j-k，得到的编号来修。（例如，n=15，a=4，b=7，第一次只有这两座塔站着，所以可选择j=7，k=4，所以和尚可以修，3和11）。现在只要判断哪个和尚没塔修，另一个和尚就赢了。
这个可以分成两种情况，一是除了站着的两座塔，其他塔都可以修，二是，除了站着的两座塔，剩下的只有部分可以修。
如果，a，b两个数其中有一个是1，或者gcd（a，b）等于1，的话，除了站着的两座塔，其他塔都可以修，所以只需要判断n的奇偶性。
如果gcd（a，b）不等于1，只能修n/gcd（a，b）座塔，所以要判断n/gcd（a，b）奇偶性。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn = 2e4 + 10;
const int mod = 1e9 + 7;
const int inf = 1e8;
#define me(a, b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
typedef long long ll;
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
int t, Case = 1;
cin >> t;
while (t--) {
int n, a, b;
cin >> n >> a >> b;
cout << "Case #" << Case++ << ": ";
if (gcd(a, b) == 1 || a == 1 || b == 1)
n % 2 ? cout << "Yuwgna" << endl : cout << "Iaka" << endl;
else
(n / gcd(a, b)) % 2 ? cout << "Yuwgna" << endl : cout << "Iaka" << endl;
}
return 0;
}
51Nod-1179 最大的最大公约数（有技巧的暴力）
题解：这个题如果用O(n^2)的做法，肯定会超时的，所以这里有种有技巧的暴力。他说要选取最大公约数，我们就从最大的一个数遍历，然后每次加一个数，如果能够加到数列中有的两个数的话，就说明这两个数的最大公约数是加的这个数。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 1e8;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int a[maxn];
int main() {
int n, l = 0;
cin >> n;
me(a, 0);
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
a[x]++;
l = max(l, x);
}
for (int i = l; l >= 1; i--) {
int s = 0;
for (int j = i; j <= l; j += i) {
s += a[j];
if (s >= 2) {
cout << i << endl;
return 0;
}
}
}
return 0;
}
HDU 5690 All X（快速幂）
题解：本题来说是一个比较难想的题，首先是能看出来这个题要用快速幂，至于怎么用，下面看分析，它给的数字是一个m为且每位都是x的数字，我们可以将数字先除以x，在乘以9，就可以化为，每位都是9的一个数，而这个数正好可以写成(10m-1)/9*x；这样就可以快速幂了。但是需要注意因为题中的k不知道是不是质数，所以不能用费马小定理。但可以用这个公式a/b%m == a%(m*b)/b，所以原式可以这样变换(10m-1)/9*x%k == c 的真假可转化为判断 (10m-1)*x%(9*k) == 9*c 。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<vector>
const int maxn = 1000010;
const int mod = 1e9 + 7;
#define me(a) memset(a,0,sizeof(a))
typedef long long ll;
using namespace std;
ll qpow(ll a, ll b, ll mod) {
ll res = 1, temp = a % mod;
while (b) {
if (b & 1)
res = res * temp % mod;
temp = temp * temp % mod;
b >>= 1;
}
return res;
}
int main() {
int t;
cin >> t;
for (int tt = 1; tt <= t; tt++) {
ll x, m, k, c;
cin >> x >> m >> k >> c;
ll s = qpow(10, m, 9 * k) - 1;
cout << "Case #" << tt << ":" << endl;
if (s * x % (9 * k) == 9 * c)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
CodeForces – 678D Iterated Linear Function（快速幂）
题解：本题就有规律的，找到规律直接快速幂就能过。个g（1）=ax+b;g（2）=a^2+ab+b；g（n）=a^n*x+b（a^n-1+a^n-2+……+a^0）;
后面可以自己多推几步就看的更加明显，这个式子可以看成两部分，前面是a的n次幂乘以x，后面是b乘以后面的一个等比数列，特别注意公比a不能为1。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<vector>
const int maxn = 1000010;
const int mod = 1e9 + 7;
#define me(a) memset(a,0,sizeof(a))
typedef long long ll;
using namespace std;
ll qpow(ll a, ll b) {
ll res = 1, temp = a % mod;
while (b) {
if (b & 1)
res = res * temp % mod;
temp = temp * temp % mod;
b >>= 1;
}
return res;
}
int main() {
ll a, b, n, x;
while (cin >> a >> b >> n >> x) {
if (a == 1)
cout << (x + n % mod * b % mod) % mod << endl;///公比不能为1
else
cout << ((x % mod * qpow(a, n) % mod) % mod +(b % mod * (1 - qpow(a, n)) % mod * qpow(1 - a, mod - 2) % mod) % mod) % mod << endl;
}
return 0;
}
POJ 2262 Goldbach’s Conjecture （素数筛选）
题解：直接先素数筛选就行了，水题。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<vector>
const int maxn = 1000010;
const int mod = 10000;
#define me(a) memset(a,0,sizeof(a))
#define ll long long
using namespace std;
bool vis[1000010];
int a[800001], l = 0;
void ss() {
for (int i = 2; i <= maxn; i++)
if (!vis[i]) {
a[l++] = i;
for (int j = i + i; j < maxn; j += i)
vis[j] = 1;
}
}
int main() {
ss();
ll n;
while (cin >> n && n) {
for (int i = 0; i < l; i++)
if (vis[n - a[i]] == 0) {
cout << n << " = " << a[i] << " + " << n - a[i] << endl;
break;
}
}
return 0;
}
HDU 4704 Sum （扩展欧拉定理）
题解：：本题s（i），就表示i位数能够组成n的种类。例如n=5，s（1）=1，因为只有一个数，s（2）=4，有（1,4），（2,3）（3,2），（4,1）。就这样，输出的是s（1）加到s（n）的和。其实列举几个就能够发现，这个是有规律的，s(i)相加最后就是2^（n-1）。所以就简单了。欧拉降幂公式///gcd(a,m)=1，那么使用欧拉定理即可：a^b≡a^(b%φ(m))(mod m) ///gcd(a,m)>1，且b>φ(m)，a^b≡a^(b%φ(m)+φ(m))(mod m)。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<vector>
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
#define me(a) memset(a,0,sizeof(a))
typedef long long ll;
using namespace std;
ll qpow(ll a, ll b) {
ll res = 1, temp = a % mod;
while (b) {
if (b & 1)
res = res * temp % mod;
temp = temp * temp % mod;
b >>= 1;
}
return res;
}
ll oula(ll n) {
ll m = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
m -= m / i;
while (n % i == 0)
n /= i;
}
}
if (n > 1)
m -= m / n;
return m;
}
int main() {
string s;
while (cin >> s) {
ll t = 0;
int d = oula(mod);
for (int i = 0; i < s.size(); i++)
t = (10 * t + s[i] - '0') % d;
cout << qpow(2, d + t - 1) << endl;
}
return 0;
}
POJ 2478 Farey Sequence （欧拉定理）
题解：可以看出后面的输出的值都是前面所有数用欧拉函数求出来的值得和，所以这样就可以提前跑一遍欧拉函数。预处理一下，后面直接输出就行了。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
const int maxn = 1e6 + 5;
const int mod = 10000;
#define me(a) memset(a,0,sizeof(a))
#define ll long long
using namespace std;
ll n, a[maxn], num[maxn];
void bol() {
me(a);
a[1] = 1;
for (int i = 2; i <= maxn; i++) {
if (!a[i])
for (int j = i; j <= maxn; j += i) {
if (!a[j])
a[j] = j;
a[j] = a[j] / i * (i - 1);
}
}
}
int main() {
bol();
for (int i = 2; i <= maxn; i++)
num[i] = num[i - 1] + a[i];
while (cin >> n && n)
cout << num[n] << endl;
return 0;
}
HDU2588 GCD（扩展欧拉定理）
题解：本题主要是要用欧拉函数。但是gcd（x,n）>=m，就是找比m大但是小于n的并且两数的公因数大于m的。这个可以转化为，等式两边同时除以一个因数，这样右边就是一个小于等于1的数，所以只要找到除以比m大的因数的，然后n在除以这个数，这样转化为gcd(n/i,i)>=1;就是找比n/i小并且与它互质的数，这就是欧拉函数了，但是注意正好i*i等于n的情况，这样只能算一次。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
const int maxn = 1e4 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;
#define me(a, b) memset(a,b,sizeof(a))
#define PI 3.1415926
#define e exp(1.0)
typedef long long ll;
using namespace std;
int ola(int n) {
int m = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
m -= m / i;
while (n % i == 0)
n /= i;
}
}
if (n > 1)
m -= m / n;
return m;
}
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
int sum = 0;
for (int i = 1; i * i <= n; i++)
if (n % i == 0) {
if (i >= m)
sum += ola(n / i);
if (n / i >= m && i * i != n)
sum += ola(i);
}
cout << sum << endl;
}
return 0;
}
HDU 5019 Revenge of GCD
题意：叫你输出他的第几个公因数，从大到小。要是没有那么多就直接输出-1.。
题解：肯定第一个是输出两个的最大公约数。其次再输出小的，可能找两个的公因数，直接跑会超时，所以我们直接找最大公因数的因数，这样复杂度就会降很多，并且在找的时候可以做一些优化，具体看代码。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<vector>
const int maxn = 2e4 + 100;
const int mod = 10000;
#define me(a) memset(a,0,sizeof(a))
#define ll long long
using namespace std;
ll gcd(ll a, ll b) {
if (!b)
return a;
return gcd(b, a % b);
}
int main() {
int t;
ll a, b, k, i;
vector<ll> q;
cin >> t;
while (t--) {
cin >> a >> b >> k;
q.clear();
ll d = gcd(max(a, b), min(a, b));
q.push_back(1);
if (d != 1)
q.push_back(d);
for (i = 2; i * i < d; i++)
if (d % i == 0) {
q.push_back(i);
q.push_back(d / i);
}
if (i * i == d)
q.push_back(i);
//cout<<q.size()<<endl;
sort(q.begin(), q.end());
if (k > q.size())
cout << "-1" << endl;
else
cout << q[q.size() - k] << endl;
}
return 0;
}
HDU 1370 Biorhythms （中国剩余定理）
题解：PS：一道中国剩余定理的题，但是暴力跑好像也能过。至于中国剩余定理，这个还是自己去网上搜博客看下，简单的说几句，肯定是说不清楚的。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<vector>
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
#define me(a) memset(a,0,sizeof(a))
typedef long long ll;
using namespace std;
ll x, y, k[3] = {23, 28, 33}, a[3];
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int gcd = exgcd(b, a % b, x, y);
int temp = x;
x = y;
y = temp - a / b * y;
return gcd;
}
ll shengyu() {
ll m = 1, sum = 0;
for (int i = 0; i < 3; i++)
m *= k[i];
for (int i = 0; i < 3; i++) {
ll mi = m / k[i];
exgcd(mi, k[i], x, y);
sum = (sum + mi * x * a[i]) % m;
}
if (sum < 0)
sum += m;
return sum;
}
int main() {
ll p, e, i, d;
int l = 1;
while (cin >> p >> e >> i >> d) {
if (p == -1 && e == -1 && i == -1 && d == -1)
break;
a[0] = p, a[1] = e, a[2] = i;
ll s = shengyu();
if (s == 0)
s = 21252;
if (s <= d)
s += 21252;
cout << "Case " << l++ << ": the next triple peak occurs in " << s - d << " days." << endl;
}
return 0;
}
HDU 4135 Co-prime（容斥定理）
题解：这个题如果用暴力直接跑a，b。肯定会超时的，所以这里我们可以用到容斥定理，我们求a，b里与n互质的个数，可以求这个范围内与n不互质的数的个数，再用总个数减去这个个数，就是答案。首先我们算1~b里与n不互质的个数，再算1~a里与n不互质的个数。两数相减，就是a~b中与n不互质的个数了。
举一组实例吧:假设m=12,n=30.。
第一步：求出n的质因子：2,3,5；
第二步：(1,m)中是n的因子的倍数当然就不互质了(2,4,6,8,10)=n/2 6个,(3,6,9,12)=n/3 4个,(5,10)=n/5 2个。6+4+2=12个了，里面明显出现了重复的,我们现在要处理的就是如何去掉那些重复的了！
第三步：这里就需要用到容斥原理了，公式就是：n/2+n/3+n/5-n/(2*3)-n/(2*5)-n/(3*5)+n/(2*3*5).
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
const int maxn = 1e4 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;
#define me(a, b) memset(a,b,sizeof(a))
#define PI 3.1415926
#define e exp(1.0)
typedef long long ll;
using namespace std;
ll a[500], l;
void ola(ll n) {
l = 0;
for (ll i = 2; i * i <= n; i++) {
if (n % i == 0)
a[l++] = i;///n的因子
while (n % i == 0)
n /= i;
}
if (n > 1)
a[l++] = n;
}
ll paici(ll m) {
ll temp[maxn], t = 0, sum = 0;
me(temp, 0);
temp[t++] = -1;
for (int i = 0; i < l; i++) {
int k = t;
for (int j = 0; j < k; j++)
temp[t++] = temp[j] * a[i] * (-1);///这步可以自己单步调试下，应该就能理解。
}
for (int i = 1; i < t; i++)
sum += m / temp[i];
return sum;
}
int main() {
int t, Case = 1;
cin >> t;
while (t--) {
ll a, b, n;
cin >> a >> b >> n;
ola(n);///找因子
ll s = b - paici(b) - (a - 1 - paici(a - 1));
cout << "Case #" << Case++ << ": " << s << endl;
}
return 0;
}
HDU 3037 Saving Beans (Lucas定理)
:题意：一共有n棵树，不超过m个果子，要将这些果子放到这些树里面，问有多少种放法（可以有树不放果子）。
题解：我们先考虑正好有m个果子有多少种放法，m个果子，n棵树的放法根据插板法得出为C(m+n-1,n-1)=C(m+n-1,m)。（插板法详解）。然后m-1的放法为C(m+n-2,m-1)，当m等于0时的放法为C(n-1,0)。
所以总的放法为C(n-1,0)+……+C(m+n-1,m)。根据排列组合公式C(n,k) = C(n-1,k)+C(n-1,k-1)。得到最终结果为，C(m+n,m)。
因为p是质数，后面就是直接用Lucas定理了。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 1e8;
#define me(a, b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
typedef long long ll;
using namespace std;
ll n, m, p, num[maxn];
void inct(ll p) {
num[0] = 1;
for (int i = 1; i <= p; i++)
num[i] = (i * num[i - 1]) % p;
}
ll quick_pow(ll a, ll b) {
ll temp = a % p, res = 1;
while (b) {
if (b & 1)
res = res * temp % p;
temp = temp * temp % p;
b >>= 1;
}
return res;
}
ll C(ll a, ll b) {
if (a < b)
return 0;
return num[a] * quick_pow(num[b] * num[a - b], p - 2) % p;
}
ll Lucas(ll a, ll b) {
if (!b)
return 1;
return C(a % p, b % p) * Lucas(a / p, b / p) % p;
}
int main() {
int t;
cin >> t;
while (t--) {
scanf("%d%d%d", &n, &m, &p);
inct(p);
printf("%lld\n", Lucas(n + m, m));
}
return 0;
}以上都是本人刚学数论时做的一些题，当时代码可能写的比较乱，希望大家不要介意！
版权声明：本文为qq_41292370原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。