LightOJ 1341 Aladdin and the Flying Carpet(合数分解)-紫杉倒影

LightOJ 1341 Aladdin and the Flying Carpet(合数分解)

紫杉数论3,58916年01月23日

题意:给定整数 a 和 b ，求区间[b, a] 内的 a 的约数的个数。

算术基本定理(唯一分解定理)

一个大于1的正整数N，如果它的标准分解式为：

，

那么它的正因数个数为

。

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<iomanip>
#include<map>
#include<vector>
#include<queue>
#include<stack>
//#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int N = 1050;

const int MAXN=1000010;
int prime[MAXN+1];

void getPrime()
{
    memset(prime,0,sizeof(prime));
    for(int i=2; i<=MAXN; ++i)
    {
        if(!prime[i])
            prime[++prime[0]]=i;
        for(int j=1; j<=prime[0] && prime[j]<=MAXN/i; j++)
        {
            prime[prime[j]*i]=1;
            if(i%prime[j]==0)
                break;
        }
    }

}

long long factor[100][2];
int fatCnt;

int getFactors(long long x)
{
    fatCnt=0;
    long long tmp=x;
    for(int i=1; prime[i]<=tmp/prime[i]; i++)
    {
        factor[fatCnt][1]=0;
        if(tmp%prime[i]==0)
        {
            factor[fatCnt][0]=prime[i];
            while(tmp%prime[i]==0)
            {
                factor[fatCnt][1]++;
                tmp/=prime[i];
            }
            fatCnt++;
        }
    }
    if(tmp!=1)
    {
        factor[fatCnt][0]=tmp;
        factor[fatCnt++][1]=1;
    }
    return fatCnt;
}

int main()
{
    getPrime();
    int t;
    cin>>t;
    int casee=1;
    LL a,b;
    while(t--)
    {
        // cin>>a>>b;
        scanf("%lld%lld",&a,&b);
        if(a/b<b)
        {
            printf("Case %d: 0n",casee++);
            continue;
        }
        int cnt=getFactors(a);
        // cout<<cnt<<endl;
        int ans=1;
        for(int i=0; i<cnt; ++i)
        {
            //cout<<factor[i][0]<<endl;
            ans*=(factor[i][1]+1); //唯一分解定理
        }
        ans>>=1;
        for(int i=1; i<b; ++i)
        {
            if(a%i==0)
            {
                ans--;
            }
        }

        printf("Case %d: %dn",casee++,ans);

    }


    return 0;
}

素数筛选和合数分解

const int MAXN=1000010;
int prime[MAXN+1];
//线性筛选
void getPrime()
{
    memset(prime,0,sizeof(prime));
    for(int i=2; i<=MAXN; ++i)
    {
        if(!prime[i])
            prime[++prime[0]]=i;
        for(int j=1; j<=prime[0] && prime[j]<=MAXN/i; j++)
        {
            prime[prime[j]*i]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}

long long factor[100][2];
//factor[i][0]==P1; factor[i][1]==a1;
//其正因子个数为S=(1+a1)(1+a2)...(1+an)
int fatCnt;

int getFactors(long long x)
{
    fatCnt=0;
    long long tmp=x;
    for(int i=1; prime[i]<=tmp/prime[i]; i++)
    {
        factor[fatCnt][1]=0;
        if(tmp%prime[i]==0)
        {
            factor[fatCnt][0]=prime[i];
            while(tmp%prime[i]==0)
            {
                factor[fatCnt][1]++;
                tmp/=prime[i];
            }
            fatCnt++;
        }
    }
    if(tmp!=1)
    {
        factor[fatCnt][0]=tmp;
        factor[fatCnt++][1]=1;
    }
    return fatCnt;
}

评分 0, 满分 5 星

0 票

评价