精华内容
下载资源
问答
  • POJ1845-Sumdiv转载请注明出处:優YoU ... 解题思路:要求有较强 数学思维 的题应用定理主要有三个:要求有较强 数学思维 的题应用定理主要有三个:(1) 整数的唯一分解定理: 任意正整数都有且只有一...

    POJ1845-Sumdiv

    转载请注明出处:優YoU  http://user.qzone.qq.com/289065406/blog/1309237394

     

    大致题意:

    求A^B的所有约数(即因子)之和,并对其取模 9901再输出。

     

    解题思路:

    要求有较强 数学思维 的题

    应用定理主要有三个:

    要求有较强 数学思维 的题

    应用定理主要有三个:

    (1)   整数的唯一分解定理:

          任意正整数都有且只有一种方式写出其素因子的乘积表达式。

          A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)   其中pi均为素数

    (2)   约数和公式:

    对于已经分解的整数A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)

    有A的所有因子之和为

        S = (1+p1+p1^2+p1^3+...p1^k1) * (1+p2+p2^2+p2^3+….p2^k2) * (1+p3+ p3^3+…+ p3^k3) * .... * (1+pn+pn^2+pn^3+...pn^kn)

    (3)   同余模公式:

    (a+b)%m=(a%m+b%m)%m

    (a*b)%m=(a%m*b%m)%m

     

    有了上面的数学基础,那么本题解法就很简单了:

    1: 对A进行素因子分解

    分解A的方法:

    A首先对第一个素数2不断取模,A%2==0时 ,记录2出现的次数+1,A/=2;

    当A%2!=0时,则A对下一个连续素数3不断取模...

    以此类推,直到A==1为止。

     

    注意特殊判定,当A本身就是素数时,无法分解,它自己就是其本身的素数分解式。

     

    最后得到A = p1^k1 * p2^k2 * p3^k3 *...* pn^kn.
          故 A^B = p1^(k1*B) * p2^(k2*B) *...* pn^(kn*B);


    2:A^B的所有约数之和为:

         sum = [1+p1+p1^2+...+p1^(a1*B)] * [1+p2+p2^2+...+p2^(a2*B)] *...* [1+pn+pn^2+...+pn^(an*B)].


    3: 用递归二分求等比数列1+pi+pi^2+pi^3+...+pi^n:

    (1)若n为奇数,一共有偶数项,则:
          1 + p + p^2 + p^3 +...+ p^n

          = (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +...+ p^(n/2) * (1+p^(n/2+1))
          = (1 + p + p^2 +...+ p^(n/2)) * (1 + p^(n/2+1))

    上式红色加粗的前半部分恰好就是原式的一半,那么只需要不断递归二分求和就可以了,后半部分为幂次式,将在下面第4点讲述计算方法。

     

    (2)若n为偶数,一共有奇数项,则:
          1 + p + p^2 + p^3 +...+ p^n

          = (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +...+ p^(n/2-1) * (1+p^(n/2+1)) + p^(n/2)
          = (1 + p + p^2 +...+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2);

       上式红色加粗的前半部分恰好就是原式的一半,依然递归求解

     

    4:反复平方法计算幂次式p^n

       这是本题关键所在,求n次幂方法的好坏,决定了本题是否TLE。

       以p=2,n=8为例

       常规是通过连乘法求幂,即2^8=2*2*2*2*2*2*2*2

       这样做的要做8次乘法

     

       而反复平方法则不同,

       定义幂sq=1,再检查n是否大于0,

    While,循环过程若发现n为奇数,则把此时的p值乘到sq

    {

       n=8>0 ,把p自乘一次, p=p*p=4     ,n取半 n=4

       n=4>0 ,再把p自乘一次, p=p*p=16   ,n取半 n=2

    n=2>0 ,再把p自乘一次, p=p*p=256  ,n取半 n=1,sq=sq*p

    n=1>0 ,再把p自乘一次, p=p*p=256^2  ,n取半 n=0,弹出循环

    }

    则sq=256就是所求,显然反复平方法只做了3次乘法

     

    1. //Memory Time   
    2. //336K   0MS   
    3.   
    4. #include<iostream>  
    5. using namespace std;  
    6.   
    7. const int size=10000;  
    8. const int mod=9901;  
    9.   
    10. __int64 sum(__int64 p,__int64 n);  //递归二分求 (1 + p + p^2 + p^3 +...+ p^n)%mod  
    11. __int64 power(__int64 p,__int64 n);  //反复平方法求 (p^n)%mod  
    12.   
    13. int main(void)  
    14. {  
    15.     int A,B;  
    16.     int p[size];//A的分解式,p[i]^n[i]  
    17.     int n[size];  
    18.   
    19.     while(cin>>A>>B)  
    20.     {  
    21.         int i,k=0;  //p,n指针  
    22.   
    23.         /*常规做法:分解整数A (A为非质数)*/  
    24.         for(i=2;i*i<=A;)   //根号法+递归法  
    25.         {  
    26.             if(A%i==0)  
    27.             {  
    28.                 p[k]=i;  
    29.                 n[k]=0;  
    30.                 while(!(A%i))  
    31.                 {  
    32.                     n[k]++;  
    33.                     A/=i;  
    34.                 }  
    35.                 k++;  
    36.             }  
    37.             if(i==2)  //奇偶法  
    38.                 i++;  
    39.             else  
    40.                 i+=2;  
    41.         }  
    42.         /*特殊判定:分解整数A (A为质数)*/  
    43.         if(A!=1)  
    44.         {  
    45.             p[k]=A;  
    46.             n[k++]=1;  
    47.         }  
    48.   
    49.         int ans=1;  //约数和  
    50.         for(i=0;i<k;i++)  
    51.             ans=(ans*(sum(p[i],n[i]*B)%mod))%mod;  //n[i]*B可能会超过int,因此用__int64  
    52.   
    53.         cout<<ans<<endl;  
    54.     }  
    55.     return 0;  
    56. }  
    57.   
    58. __int64 sum(__int64 p,__int64 n)  //递归二分求 (1 + p + p^2 + p^3 +...+ p^n)%mod  
    59. {                          //奇数二分式 (1 + p + p^2 +...+ p^(n/2)) * (1 + p^(n/2+1))  
    60.     if(n==0)               //偶数二分式 (1 + p + p^2 +...+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2)  
    61.         return 1;  
    62.     if(n%2)  //n为奇数,  
    63.         return (sum(p,n/2)*(1+power(p,n/2+1)))%mod;  
    64.     else     //n为偶数  
    65.         return (sum(p,n/2-1)*(1+power(p,n/2+1))+power(p,n/2))%mod;  
    66. }  
    67.   
    68. __int64 power(__int64 p,__int64 n)  //反复平方法求(p^n)%mod  
    69. {  
    70.     __int64 sq=1;  
    71.     while(n>0)  
    72.     {  
    73.         if(n%2)  
    74.             sq=(sq*p)%mod;  
    75.         n/=2;  
    76.         p=p*p%mod;  
    77.     }  
    78.     return sq;  
    79. }  
    展开全文
  • 先介绍整数的唯一分解定理: 即: 任意大于1的正整数都可以唯一分解成若干素数的乘积。 而本题的素数因子只能是2,3,5,所以抽数必定是如下形式: x=2p∗3q∗5rx = 2^p* 3^q*5^rx=2p∗3q∗5r,其中 p,q,r为非负整数p,...

    原题:https://vjudge.net/problem/UVA-136

    题目大意
    在这里插入图片描述
    题目分析

    先介绍整数的唯一分解定理:
    在这里插入图片描述
    即:
    任意大于1的正整数都可以唯一分解成若干素数的乘积。

    而本题的素数因子只能是2,3,5,所以抽数必定是如下形式:
    x=2p3q5rx = 2^p* 3^q*5^r,其中 p,q,rp,q,r为非负整数

    所以,我们可以从1开始依次生成丑数,每次将生成的丑数与2,3,5因子相乘生成新的丑数,但是我们生成的丑数需要从小到大排列,所以我们使用优先队列存储生成的丑数,并且每次取出最小的丑数来继续生成。

    注意,丑数的生成方式可能并不唯一,因为一个丑数可能同时是2,3,5的倍数,所以我们需要判断生成的丑数是否重复,用setmap均可。

    /* 丑数的生成 */
    // 找出第1500个素数
    #include<iostream>
    #include<functional>
    #include<set>
    #include<queue>
    
    using namespace std;
    
    typedef long long LL;
    
    int coef[3] = { 2,3,5 }; // 3个素数因子
    set<LL> cnt; // 拿来判断该数字是否生成过
    priority_queue<LL,vector<LL>,greater<LL>> q; // 生成的数字,每次取最小的数字继续生成
    
    int main() {
    	int i;
    	LL x = 1;
    	q.push(x);
    	cnt.insert(x);
    	for (i = 1;; i++) {
    		x = q.top(); q.pop();
    		if (i == 1500) {
    			printf("The 1500'th ugly number is %ld.\n", x);
    			break;
    		}
    		for (int j = 0; j < 3; j++) {
    			LL ans = coef[j] * x;
    			if (cnt.count(ans) == 0) {
    				cnt.insert(ans); q.push(ans);
    			}
    		}
    	}
    	return 0;
    }
    
    展开全文
  • 思路:任何一个大于1的自然数,都可以唯一分解成有限个质数的乘积,这里均为质数,其诸指数是正整数。那么它的正因数个数为,那么 ,由于​k​​)=(kc​1​​+1)(kc​2​​+1)...(kc​m​​+1)。l 和 r 的是到10的12...

    题意:定义d(x)是数字x正因子的个数,给你l,r,k,求

    思路:任何一个大于1的自然数,都可以唯一分解成有限个质数的乘积,这里均为质数,其诸指数是正整数。那么它的正因数个数为,那么 ,由于k​​)=(kc1​​+1)(kc2​​+1)...(kcm​​+1)。l 和 r 的是到10的12次方,一个非质数肯定能由 √r 以下的质数表示出来,所以我们可以将0~10^6的素数筛出来,枚举 2~√r 的所有素数p,再枚举区间[l,r]中所有p的倍数,将其分解质因数,如果最后剩下的数大于1说明是大于√r的质数

    代码:

    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #define ll long long
    
    using namespace std;
    
    const ll mod = 998244353;
    const int maxn = 1e6+10;
    bool isprime[maxn];
    ll prime[maxn];
    ll data[maxn];
    ll fac[maxn];
    int tot;
    
    void get_prime()
    {
        memset(isprime,true,sizeof(isprime));
        tot=0;
        for(ll i=2;i<maxn;i++)
        {
            if(isprime[i])
            {
                prime[tot++]=i;
                for(ll j=i*i;j<maxn;j+=i)
                {
                    isprime[j]=false;
                }
            }
        }
    }
    
    int main()
    {
        get_prime();
        int t;
        cin>>t;
        while(t--)
        {
            ll l,r,k;
            cin>>l>>r>>k;
            for(ll i=0;i<(r-l+1);i++)
            {
                data[i]=i+l;
                fac[i]=1;
            }
            for(int i=0;i<tot&&prime[i]*prime[i]<=r;i++)
            {
                ll p=l-l%prime[i];
                if(p<l) p=p+prime[i];
                for(ll j=p;j<=r;j=j+prime[i])
                {
                    ll cnt=0;
                    ll wei=j-l;
                    while(data[wei]%prime[i]==0)
                    {
                        cnt++;
                        data[wei]=data[wei]/prime[i];
                    }
                    fac[wei]=(fac[wei]*(cnt*k%mod+1))%mod;
                }
            }
            ll ans=0;
            for(int i=0;i<(r-l+1);i++)
            {
                if(data[i]>1) fac[i]=fac[i]*(k+1)%mod;
                ans=(ans+fac[i])%mod;
            }
            cout<<ans<<endl;
        }
    }
    (i=lrd(ik))mod99824435
    (i=lrd(ik))mod9982443
    (i=lrd(ik))mod998244353

    转载于:https://www.cnblogs.com/simplekinght/p/7283849.html

    展开全文
  • ll phi(int x)//根据推出的公式:(6*t1)*(6*t2)*........(6*tn),ti代表第i个因子的指数,分解质因子。 { ll ans=1; for(int i=2;i*i;i++) { int tmp=0; if(x%i==0) { while(x%i==0) { tmp++; ...

    Given two positive integers G and L, could you tell me how many solutions of (x, y, z) there are, satisfying that gcd(x, y, z) = G and lcm(x, y, z) = L? 
    Note, gcd(x, y, z) means the greatest common divisor of x, y and z, while lcm(x, y, z) means the least common multiple of x, y and z. 
    Note 2, (1, 2, 3) and (1, 3, 2) are two different solutions.

    Input

    First line comes an integer T (T <= 12), telling the number of test cases. 
    The next T lines, each contains two positive 32-bit signed integers, G and L. 
    It’s guaranteed that each answer will fit in a 32-bit signed integer.

    Output

    For each test case, print one line with the number of solutions satisfying the conditions above.

    Sample Input

    2 
    6 72 
    7 33 

    Sample Output

    72 
    0

    题意:

    这个博客写的比较清楚,只是感觉最后的公式写错了。

     

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    #include<queue>
    #include<stack>
    #include<map>
    #include<set>
    #include<string>
    #include<vector>
    #define mod (1000000007)
    using namespace std;
    typedef long long ll;
    
    ll phi(int x)//根据推出的公式:(6*t1)*(6*t2)*........(6*tn),ti代表第i个因子的指数,分解质因子。
    {
    	ll ans=1;
    	for(int i=2;i*i<=x;i++)
    	{
    		int tmp=0;
    		if(x%i==0)
    		{
    			while(x%i==0)
    			{
    				tmp++;
    				x/=i;
    			}
    			ans*=6*tmp;
    		}
    	}
    	if(x!=1)
    	ans*=6;
    	return ans; 
    }
    int main() 
    {
    	int t;
    	cin>>t;
    	while(t--)
    	{
    		int G,L;
    		scanf("%d%d",&G,&L);
    		if(L%G!=0)//如果L与G互质,那么找不出符合条件的数
    			printf("0\n");
    		else//否则就可以将问题转换为满足gcd(x,y,z)=1&&lcm(x,y,z)=L/G的数的组合有多少
    		{
    			int x=L/G;
    			printf("%d\n",phi(x));
    		}
    	} 
    
    	return 0;
    }

    推理部分:来自该博客

    首先如果L不能被G整除的话,这样的组合一定不存在。

      当这样的组合存在的时候,所求与  求gcd(x,y,z)=1且lcm(x,y,z)=L/G的方法数是等价的。

      那么:令temp=L/G。

      对temp进行素数分解:temp=p1^t1 * p2^t2 * ……* pn^tn。

      因为temp是这三个数的倍数,因而x,y,z的组成形式为:

      x=p1^i1 * p2^i2 *…… * pn^in;

      y=p1^j1 * p2^j2 *…… * pn^jn;

      z=p1^k1 * p2^k2 * …… * pn^kn;

      对于某一个素因子p:

              因为要满足x,y,z的最大公约数为1,即三个数没有共同的素因子,所以min(i,j,k)=0。

              又因为要满足x,y,z的最小公倍数为temp,即p^t必然要至少存在一个,所以max(i,j,k)=t。

              换言之:至少要有一个p^t,以满足lcm的要求;至多有两个包含p,以满足gcd的要求。

              因而基本的组合方式为(0,p^t,p^k),k=0-->t。

              而因为(1,2,3)和(2,1,3)是不同的方法,所有满足要求的方法中,除了(0,0,t)和(0,t,t)各有3种排列之外,其余都有6种排列。

              对于某一个素因子p总的方法数为6*(t-1)+2*3=6*t。

    最终答案为(6*t1)*(6*t2)*........(6*tn)。

    展开全文
  • A - (例题)整数分解 Crawling in process... Crawling failed Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu Submit Status Description Find the result of the following ...
  • 【ACM】整数唯一分解定理

    千次阅读 2016-12-18 22:00:57
    (称为标准分解式)其中pi为素数,质数ai为正整数(如果ai=0,相当于乘一,没有意义的)。标准分解式是唯一且一定存在的。(素因子的乘积顺序不考虑)下面给出几个简单的判别式: 整数a能被2整除的充要条件是a的末尾...
  • C - (例题)整数分解,计数 Crawling in process... Crawling failed Time Limit:1000MS Memory Limit:65535KB 64bit IO Format:%I64d & %I64u Submit Status Description Given two positive ...
  • 算术基本定理,又称为正整数的唯一分解定理,即:每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。例如:   算术基本定理的内容由两部分构成: 分解的存在性; 分解的唯一...
  • (1)整数唯一分解定理: 任意一个整数都可以写成素数相乘的形式 A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn) 其中pi均为素数  (2)约数: S = (1+p1+p1^2+p1^3+...p1^k1) * (1+p2+p2^2+p2^3+….p2^k2) * (1...
  • 标准算法则是应用正整数唯一分解定理,将n唯一分解后,它的所有因子和实际上就是(a1^0+a2^0...)(a2^0....)...... 即各种排列组合的和,又因为不包含本身,所以最后减去n; 代码: #include #include ...
  • 给一个正整数n,将n分解为质因数。 说明:n的质因数要么是n本身(n是素数),要么一定小于等于sqrt(n)。因此可以用小于等于sqrt(n)的数对n进行试... 1 //整数的唯一分解定理 2 int a[10000];//表示第i个质因数...
  • ,n和m的范围为0到1000000,直接递归求解的话肯定会T,因此这里需要利用整数唯一分解定理进一步化简。  首先可以根据素数筛法找到不超过(n + m)之内的素数并存到数组 prime 中,然后对于每一个素数 prime [i]再...
  • 定理:任意大于1的整数都能表示成素数的乘积,即对任一整数a > 1,有 a = p1­p­2…pn , p1­ 并且表达式是唯一的。 p[i] = k, 表示i这个质因子有k个 定义:在数论,对正整数n,欧拉函数是小于等于n的数...
  • 整除性 1. 整除的定义:a\small aa整除b  ⟺  \small b \iffb⟺b\small bb能被a\small aa整除  ⟺  \small \iff⟺a∣b  ⟺  ∃ q,b=aq\small a \mid b\iff \exist ~q,b=aqa∣b⟺∃ ...
  • Mysterious Bacteria LightOJ - 1220Dr. Mob has just discovered a Deathly Bacteria. He named it...
  • 唯一分解定理

    2021-02-14 08:20:05
    整数的唯一分解定理 对于一个大于1正整数n可以分解质因数:
  • 思路:这道题的精髓是运用了整数的唯一分解定理,求约数,倍数,质因数,gcd,lcm,都应该想到这个定理。 下面解释为什么: 我们假设( a , b ) = n ,那么: 我们把每个数都分解开看一下有什么规律 n = p1^a1 * p2^...
  • problemId=1189 思路:通常这种题目,x和y都具有轮换性时,就要特别注意了 通常最后式子能化简成一个具有轮换性的式子,比如这题,化简后得到 所以我们只需要对求约数个数,就...只要对质因数分解,由于有一个平方,
  • 整数分解

    千次阅读 2018-08-14 00:26:34
    整数分解 在数学中,整数分解(英语:integer factorization)又称素因数分解(prime factorization),是将一个正整数写成几个约数的乘积。例如,给出45这个数,它可以分解成9×5。根据算术基本定理,这样的分解...
  • 整数的唯一分解 就是把一个数分解质因数。 朴素分解法 LL a; int p[maxn],e[maxn],num; int getZys(LL a, int *p , int *e ) { int num= 0 ; int m= sqrt (a+ 0.5 ); //所有的取根号都要...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,142
精华内容 456
关键字:

整数分解定理