(数论)素数和因式分解hdu-2136；hdu-1492;hdu-1215;hdu1452;hdu-

2019-04-14 08:14发布

站内文章 / 模拟电子
17891 0 1528
HDU-2136 题目大意： 给出一个数n，将其分解为质因数的形式，问分解出来最大的质数在素数表中的位置是多少。 题解： 直接进行素数筛，在素数筛中进行判断每个数，在素数筛的第二层for循环中是寻找素数i的倍数的，那么也就是j能被素数i整除，也就是j能分解出i来，然后充计j找一个大的素数进行保存下来。 #include #include #include #include #include #include using namespace std; int vis[1000005]; int pri[1000005]; int top; void prime() { int n=1000001; memset(vis,0,sizeof(vis)); pri[1]=0; top=0; for(int i=2;i<=n;i++) { if(!vis[i]) { ++top; pri[i]=top; for(int j=i*2;j<=n;j+=i) { vis[j]=1; pri[j]=top; } } } } int main() { int n; prime(); while(scanf("%d",&n)!=EOF) { printf("%d ",pri[n]); } return 0; }
HDU-1492 题目大意： 给出一个数n，这个数只能分解出2,3,5或者7这四个数中的几个。然后求这个数的约数的个数。 题解： 那么就充计一下2,3,5,7各有多少个就行。然后进行约数个数公式 若n被分解为:n=p1^a1p2^a2....,，那么正约数的个数=（a1+1）*(a2+1)**** 本来以为这个题会因为只包含2的情况下会超时的，就对2进行的log求解，结果没有超时。 #include #include #include #include #include using namespace std; typedef long long LL; int main() { LL n; while(scanf("%lld",&n),n) { LL a,b,c,d; a=b=c=d=1; while(n%7==0) { n=n/7; a++; } while(n%5==0) { n=n/5; b++; } while(n%3==0) { n=n/3; c++; } // while(n%2==0) // { // n=n/2; // d++; // } d+=(LL)log2(n); //cout<

 HDU-1215 题解： 就是求一下因子和，用一下求因子和的公式，比较裸了，用一下等比数列求和。就不在赘述了。 #include #include #include #include #include #include using namespace std; typedef long long LL; int main() { int t; int n; scanf("%d",&t); while(t--) { scanf("%d",&n); int m=n; LL ans=1; for(int i=2;i<=sqrt(n);i++) { if(n%i==0) { int sum=0; while(n%i==0) { n=n/i; sum++; } LL ant=(1-(LL)pow(i,sum)*i)/(1-i); ans=ans*ant; } } if(n!=1)ans*=(1+n); printf("%lld ",ans-m); } return 0; }

HDU-1452 题目大意：
给出x,然后求一下2004^x的因子和对29取余。
题解：
这个本来是直接求的来，然后tle了，就发现既然取余应该会有循环节吧，那就有了。打表找一下循环节求出就行了。
其实这个题也可以找出2004的素因子然后枚举
用快速幂+等比数列求和。
 #include #include #include #include #include using namespace std; typedef long long LL; int c[]={6,16,8,10,25,7,14,3,23,17,13,17,0,27,7,14,15,17,26,26,20,17,9,22,22,23,0,1}; //int p[50],a[50]; //int top; //void init() //{ // int n=2004; // top=0; // for(int i=2; i<=sqrt(n); i++) // { // if(n%i==0) // { // int ant=0; // while(n%i==0) // { // n=n/i; // ant++; // } // p[++top]=i; // a[top]=ant; // } // } // if(n!=1) // { // p[++top]=n; // a[top]=1; // } //} //LL pow1(int a,int n,int m) //{ // if(n==0)return 1; // int x=pow1(a,n/2,m); // LL ans=(LL)x*x%m; // if(n%2==1)ans=ans*a%m; // return ans; //} int main() { int x; //init(); //x=0; //int y=16; // while(x<35) // { // x++; // LL ans=1; // for(int i=1; i<=top; i++) // { // LL ant=1; // for(int j=1; j <= x*a[i]; j++) // { // ant+=pow1(p[i],j,29); // ant=ant%29; // } // ant%=29; // ans=ans*ant; // ans%=29; // } // printf("%lld,",ans); //// if(ans==16&&y==6) //// { //// cout<
HDU-1005
题目大意：
根据题目中的方程求出f（n）
题解：
又是取余的，找一下循环节。但是需要注意的是不一定是在1,1位置开始的，
我判定1,1位开始的时候有的数据是找不到的，那就从第三个位置开始了，当n==1==2时特判断一下。
 #include #include #include #include #include using namespace std; int c[10005]; int main() { int a,b,n; while(~scanf("%d%d%d",&a,&b,&n)) { if(!a&&!b&&!n)break; if(n==1||n==2) { printf("1 "); continue; } int i; c[0]=(a*1+b*1)%7;///循环节不一定从1,1开始 c[1]=(a*c[0]+b*1)%7; //cout<HDU-1852
题目大意：
给出一个n，求出2008^n的因数和再对k取余，在求出2008^m%k。
题解：
重点在于这个因数和怎么求？用因数和公式，那就要先把2008分解了，然后发现2008的质因数只有2和251，
那么就枚举这两个质因数进行等比数列+快速幂求和了。注意在进行等比数列取模的时候，因为涉及到除法的取模，
要注意。
#include #include #include #include #include #include using namespace std; typedef long long LL; LL pow1(LL a,LL n,LL m) { if(n==0)return 1; LL x=pow1(a,n/2,m); x=x*x%m; if(n%2==1)x=x*a%m; return x; } int main() { LL n,k; while(~scanf("%lld%lld",&n,&k)) { if(!n&&!k)break; LL sum1=pow1(2,3*n+1,250*k)-1;///求因子和用等比数列求和 ///有两个等比数列求和公式 ///因为sum1和sum2要相乘，所以取模的话sum1也要按除法的来 LL sum2=pow1(251,n+1,250*k)-1;///除法的取模 //sum2=sum2/250; LL m=(sum1*sum2)%(250*k); m=m/250; LL ans=pow1(2008,m,k); printf("%lld ",ans); } return 0; }

热门文章