加载中…
个人资料
微博
  • 博客等级：
  • 博客积分：
  • 博客访问：
  • 关注人气：
  • 获赠金笔：0支
  • 赠出金笔：0支
  • 荣誉徽章：
正文 字体大小：大 中 小

poj && hdu 数论、筛法、欧拉函数等水题集

(2013-06-11 19:14:37)
标签：

hdu

poj

 分类： Algorithm
话说自从上次被wangyx神犇的“有趣的数学题”们虐了以及被鄙视不会筛欧拉函数不会筛约数以后，就决定找一些乱七八糟的数论水题来找虐，有益身心健康= =
里面讲的非常详细了，这里就不多扯了。
放水题。

hdu 2824
裸线性筛欧拉函数，不多说。煞笔在了忘记多组数据= =
还有一点就是内存限制无法直视啊，只能各种减常数非常不爽。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define N 3000010
int a,b,cnt;
int prime[N];
bool pd[N];
long long E[N];
int main(){
   E[1] = 1;
   for (int i = 2;i < N;i ++){
       if (!pd[i]){
           prime[cnt ++] = i;
           E[i] = i - 1;
       }
       for (int j = 0;j < cnt && i * prime[j] < N;j ++){
           pd[i * prime[j]] = 1;
           if (i % prime[j] == 0){
               E[i * prime[j]] = E[i] * prime[j];
               break;
           }else{
               E[i * prime[j]] = E[i] * (prime[j] - 1);
           }
       }
   }
   for (int i = 1;i < N;i ++) E[i] += E[i - 1];
   while (scanf("%d%d",&a,&b) != EOF){
       cout << E[b] - E[a - 1] << endl;
   }
   return 0;
}

poj 2992
求Cn,k的约数个数。
在没学逆元的时候，算组合数就是先搞成阶乘的样子傻傻地将其分解质因数然后约啊约的。这道题也是借鉴了那个思想，先预处理一个数对于每个质数的次数，然后由于有阶乘就求个前缀和。计算的时候减一减乘起来就行了。
然后预处理也是可以像前面题目那样筛过去的。理解了那个筛法的原理就很容易迁移到这个上面了。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define LL long long
#define N 440
int prime[N];
bool pd[N];
int A[N][N];
int main(){
   int cnt = 0,flag;
   for (int i = 2;i <= 431;i ++){
       if (!pd[i]){
           prime[cnt ++] = i;
           A[i][cnt - 1] = 1;
       }
       flag = 1;
       for (int j = 0;j < cnt && i * prime[j] <= 431 && flag;j ++){
           pd[i * prime[j]] = 1;
           if (i % prime[j] == 0){
               A[i * prime[j]][j] = A[i][j] + 1;
               flag = 0;
           }else{
               A[i * prime[j]][j] = 1;
           }
           for (int k = j + 1;k < cnt;k ++)
               A[i * prime[j]][k] = A[i][k];
       }
   }
   for (int i = 2;i <= 431;i ++){
       for (int j = 0;j < cnt;j ++) A[i][j] += A[i - 1][j];
   }
   int a,b;
   LL ans;
   while (scanf("%d%d",&a,&b) != EOF){
       ans = 1;
       for (int j = 0;j < cnt;j ++){
           ans *= (LL) (A[a][j] - A[b][j] - A[a - b][j] + 1);
       }
       cout << ans << endl;
   }
   return 0;
}

poj 2480
求∑gcd(i, N) 1<=i <=N。
这道题看到的时候稍微yy了一下发现要求的就是F[N] = Σp*phi(N/p) [p为N的约数，phi()为欧拉函数]。
具体怎么yy的呢，就是想，gcd(i,N)==1的数有phi(N)个，gcd(i,N)==2的数有phi(N/2)个...gcd(i,N)==N的数有phi(N/N)个。不是很严谨不过可以很容易理解= =
然后就不会了。去看了网上神犇们的题解知道了有种东西叫做积性函数。
这道题要求的这货就是积性函数。
虽然我自己没有好好看懂证明。不过稍微带几个进去yy一下发现好像是这样。
然后就把N分解质因数拆成N=p1^k1 * p2^k2 * ... * pn^kn [p都是质数]
于是：F[N] = F[p1^k1] * F[p2^k2] * ... * F[pn^kn]
具体到F[p^k]怎么算。
我们结合一开始导出的公式稍微yy一下，可以发现：F[p^k]=Σp^i * phi(p^(k-i))。[i属于0到k]
由于我们知道一个公式：phi(p^k) = p^k - p^(k-1) [p为质数，k>0]
那么带进去稍微化一化，就可以得到：F[p^k] = k * (p^k - p^(k-1)) + p^k
于是就解决了。
预处理筛出质数。每次对n因式分解后计算答案就可以了。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define N 100010
int prime[N],fac[N],fac1[N],K[N];
bool pd[N];
int cnt,c,n;
void get(int n){
   int tmp = n;
   for (int i = 0;prime[i] * prime[i] <= n && i < cnt && tmp > 1;i ++)
       if (tmp % prime[i] == 0){
           fac[c] = 1;K[c] = 0;
           while (tmp % prime[i] == 0) tmp /= prime[i],fac[c] *= prime[i],K[c] ++;
           fac1[c] = fac[c] / prime[i];
           c ++;
       }
   if (tmp > 1) fac[c] = tmp,fac1[c] = 1,K[c ++] = 1;
}
int main(){
   cnt = 0;
   for (int i = 2;i < N;i ++){
       if (!pd[i]) prime[cnt ++] = i;
       for (int j = 0;j < cnt && i * prime[j] < N;j ++){
           pd[i * prime[j]] = 1;
           if (i % prime[j] == 0) break;
       }
   }
   long long ans;
   while (scanf("%d",&n) != EOF){
       c = 0;
       get(n);
       ans = 1;
       for (int i = 0;i < c;i ++)
           ans = ans * ((long long)K[i] * fac[i] + fac[i] - (long long)K[i] * fac1[i]);
       cout << ans << endl;
   }
   return 0;
}

poj 2773
读入N,K，求与N互质的第K个正整数。
一种方法就是由于这些正整数存在以N为周期加上去的，那么先求出小于等于N的表，然后算K是在它周期的第几个就行了。比较显然。
这里介绍一种二分答案+容斥的想法。
对于二分出的一个数num，我们考虑怎么求小于等于它的与N互质的数。
我们可以转化成求num - 小于等于它的与N不互质的数。
假设N分解质因数以后是N = p1^k1 * p2^k2 * ... pn^kn
那么容斥的思路就是：与N不互质的数 = Σ（以pi为约数的数的个数） - Σ（以pi*pj为约数的数的个数）+ Σ（以pi*pj*pk为约数的数的个数）...
以某个数t为约数的数的个数就是N/t。这点显然的对不对。
本来以为答案会爆int，结果发现好像不会，二分上界只要10^9就够了。
二分的时候退出条件的控制这个细节也是很重要的。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define N 1010
bool pd[N];
int prime[N],fac[N];
int cnt,c,n,K;
void get(int n){
   int tmp = n;
   for (int i = 0;i < cnt && prime[i] * prime[i] <= n && tmp > 1;i ++)
   if (tmp % prime[i] == 0){
       fac[c ++] = prime[i];
       while (tmp % prime[i] == 0) tmp /= prime[i];
   }
   if (tmp > 1) fac[c ++] = tmp;
}
int judge(int num){
   int sum = 0;
   for (int i = 1;i < (1 << c);i ++){
       int t = 0;
       int tmp = 1;
       for (int j = 0;j < c;j ++) if ((i >> j) & 1){
           tmp *= fac[j];
           t ++;
       }
       if (t % 2) sum += num / tmp;
       else sum -= num / tmp;
   }
   return num - sum;
}
int main(){
   for (int i = 2;i < N;i ++){
       if (!pd[i])    prime[cnt ++] = i;
       for (int j = 0;j < cnt && i * prime[j] < N;j ++){
           pd[i * prime[j]] = 1;
           if (i % prime[j] == 0) break;
       }
   }
   while (scanf("%d%d",&n,&K) != EOF){
       c = 0;get(n);
       int l = 0,r = 1000000000,mid,ans;
       while (l < r - 1){
           mid = l + r >> 1;
           int tmp = judge(mid);
           if (tmp >= K){
               if (tmp == K) ans = mid;
               r = mid;
           }else l = mid;
       }
       printf("%d\n",ans);
   }
   return 0;
}

hdu 1695
求x属于[1,b]，y属于[1,d]，且gcd(x,y)==k的无序数对(x,y)的数量。
稍微yy一下可以发现其实求的就是x属于[1,b/k],y属于[a,d/k]且x,y互质的数对的数量。
那么b/=k,d/=k。我们再假定b<d。
枚举i从1到d，对于i求的就是小于等于min(i,b)的数中与i互质的数的个数。
当i<=b的时候，这个个数就是phi(i)。
当i>b的时候，这个个数可以通过类似上一道题目的容斥来做。
预处理的时候把欧拉函数和各个数的约数都要筛出来。
我又要说hdu的内存限制丧心病狂了。以及，k居然会等于0简直就不能忍了= =
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#define N 100010
int prime[N],E[N],fac[N][50];
bool pd[N];
int cnt,a,b,c,d,k;
void pre(){
   int flag;
   E[1] = 1;
   for (int i = 2;i < N;i ++){
       if (!pd[i]) {
           prime[cnt ++] = i;
           E[i] = i - 1;
           fac[i][++ fac[i][0]] = i;
       }
       flag = 1;
       for (int j = 0;flag && j < cnt && i * prime[j] < N;j ++){
           pd[i * prime[j]] = 1;
           for (int k = 1;k <= fac[i][0];k ++) fac[i * prime[j]][k] = fac[i][k];
           fac[i * prime[j]][0] = fac[i][0];
           if (i % prime[j] == 0){
               E[i * prime[j]] = E[i] * prime[j];
               flag = 0;
           }else {
               E[i * prime[j]] = E[i] * (prime[j] - 1);
               fac[i * prime[j]][++ fac[i * prime[j]][0]] = prime[j];
           }
       }
   }
}
long long work(int x,int num){
   int c = fac[x][0];
   long long sum = 0;
   for (int i = 1;i < (1 << c);i ++){
       int tmp = 1;
       int t = 0;
       for (int j = 0;j < c;j ++) if ((i >> j) & 1){
           t ++;
           tmp *= fac[x][j + 1];
       }
       if (t % 2) sum += num / tmp;
       else sum -= num / tmp;
   }
   return num - sum;
}
int main(){
   cnt = 0;
   pre();
   long long ans;
   int T,Case = 0;
   scanf("%d",&T);
   while (T --){
       scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
       if (k == 0) {printf("Case %d: 0\n",++ Case);continue;}
       b /= k,d /= k;
       ans = 0;
       if (b > d) swap(b,d);
       for (int i = 1;i <= b;i ++) ans += E[i];
       for (int i = b + 1;i <= d;i ++){
           ans += work(i,b);
       }
       printf("Case %d: ",++ Case);
       cout << ans << endl;
   }
   return 0;
}


喜欢

0

阅读┊ 收藏 ┊ 喜欢▼ ┊打印┊举报/Report
  

新浪BLOG意见反馈留言板　欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

Copyright © 1996 - 2022 SINA Corporation, All Rights Reserved

新浪公司 版权所有