hdu6069 Counting Divisors lightoj1028 - Trailing Zeroes (I)

本文主要是介绍hdu6069 Counting Divisors lightoj1028 - Trailing Zeroes (I)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

由易到难：lightoj1028->hdu6069

lightoj1028 : http://www.lightoj.com/volume_showproblem.php?problem=1028

求一个数n，有多少种进制表示方法，使得末尾为0.

我们首先要想到这个n转化为其他进制如果末尾是0的话，只需要n可以整除这个数，换言之就是求n这个数在2-n范围内的约数。如果n很小的话（n<1e6）可以直接暴力遍历一次，但是n的范围是1e12，这个时候我们可以这样做。 n=px11∗px22∗px33... 其中 pi 是素数， xi 为正整数，这样我们就能算出约数的个数了。。。 
answer=(x1+1)∗(x2+1)∗...−1

所以最后所求的就是打好一个1e6的素数表，然后用这个公式直接求就可以了。

（这里举一个例子）：

所以2004的约数个数是ans=(2+1）*（1+1）*（1+1）=12； 最后减去1.因为没有1进制；

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 1e6+10;
ll prime[N];
ll num;void getPrime()
{memset(prime,0,sizeof(prime));//一开始prime都设为0代表都是素数（反向思考）for(int i=2;i<=N;i++){if(!prime[i])prime[++prime[0]]=i;for(int j=1;j<=prime[0]&&prime[j]<=N/i;j++){prime[prime[j]*i]=1;//prime[k]=1；k不是素数if(i%prime[j]==0)break;}}
}int main()
{getPrime();int T;int cas=1;scanf("%d",&T);ll n;while(T--){ll n ,temp,ans = 1;scanf("%lld",&n);for(int i = 1;(prime[i]*prime[i]<=n&&i<=prime[0]);i++){if(n%prime[i]==0){temp=0;while(n%prime[i]==0){temp++;n/=prime[i];}ans*=(temp+1);}}if(n>1) ans*=2;printf("Case %d: %lld\n",cas++,ans-1);  }
}

下面看一下hdu6069：http://acm.hdu.edu.cn/showproblem.php?pid=6069

所以还是一个对于n的分解问题，这里有一个用到的就是区间映射，从l到r拿0到r-l对应。中间遍历时先遍历素数表，假设现在遍历到prime[i],先找到l~r第一个能整除prime[i]的数a[j],以此开始，每次下标加prime[i],在分解a[j]时一直除以prime[i]直到除不尽，这时已经消除了prime[i]因子，把分解的幂值加进sum[j]。

代码如下：

#include<bits/stdc++.h>
#define ll long long 
#define mod 998244353
using namespace std;const int maxn = 1e6+10;
ll tot,t;  
ll l,r,k,ans,cnt[maxn],q[maxn],primes[maxn];
ll prime[maxn];void getPrime()
{memset(prime,0,sizeof(prime));//一开始prime都设为0代表都是素数（反向思考）for(ll i=2;i<=maxn;i++){if(!prime[i])prime[++prime[0]]=i;for(ll j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){prime[prime[j]*i]=1;//prime[k]=1；k不是素数if(i%prime[j]==0)break;}}
}int main()
{getPrime();scanf("%d",&t);  while(t--){scanf("%lld%lld%lld",&l,&r,&k);ans = 0 ;if(l==1)	ans++,l++;for(ll i=0;i<=r-l;i++)	cnt[i]=1,q[i]=l+i;for(ll i=1;prime[i]*prime[i]<=r&&i<=prime[0];i++){ll j=l/prime[i]+(l%prime[i]!=0);for(j=j*prime[i];j<=r;j+=prime[i]){ll temp=0;while(q[j-l]%prime[i]==0) q[j-l]/=prime[i],temp++;cnt[j-l]*=(temp*k)%mod+1,cnt[j-l]%=mod; }} for(ll i=0;i<=r-l;i++){if(q[i]!=1)	ans+=((k+1)*cnt[i])%mod;else ans+=cnt[i];ans%=mod;}printf("%lld\n",ans);  }return 0;
}

这篇关于hdu6069 Counting Divisors lightoj1028 - Trailing Zeroes (I)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---