锐客网

  1. 首页 > it技术 > >

HDU|HDU 5528 Count a * b(线性筛+积性函数)

去年长春赛区的B题，金牌数论题
我用了比较丑陋的方法过的，其实这题可以推导
但是看了人家推的，除了叉姐的我看得懂，其他人的我都看不懂
先打个表看下里面0和非0元素的个数把
很快就发现，如果一个数字不是全是一个因子的次方的话，拆成两个互质的数相乘即可
如果是xn的话，这得好好观察，经验来说一般有公式
f[xn+1]=x?f[xn]+m
凑一下这个m就好了
当然这题还没那么简单，n是109，所以需要先筛因子，然后对于每个因子，求这个公式
考虑到因子很大，可以用递归，100W以下打表，以上的话就筛最小的素因子
跑得比较慢，但是考虑到比赛时候是应该能过的
【HDU|HDU 5528 Count a * b(线性筛+积性函数)】代码

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #pragma comment(linker,"/STACK:102400000,102400000")using namespace std; #defineMAX1000005 #defineMAXN1000005 #definemaxnode105 #definesigma_size30 #definelsonl,m,rt<<1 #definersonm+1,r,rt<<1|1 #definelrtrt<<1 #definerrtrt<<1|1 #definemiddleint m=(r+l)>>1 #defineLLlong long #defineullunsigned long long #definemem(x,v)memset(x,v,sizeof(x)) #definelowbit(x)(x&-x) #definepiipair #definebits(a)__builtin_popcount(a) #definemkmake_pair #definelimit10000//const intprime = 999983; const intINF= 0x3f3f3f3f; const LLINFF= 0x3f3f; const double pi= acos(-1.0); const double inf= 1e18; const double eps= 1e-8; const LLmod= 1e9+7; const ullmx= 133333331; /*****************************************************/ inline void RI(int &x) { char c; while((c=getchar())<'0' || c>'9'); x=c-'0'; while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0'; } /*****************************************************/bool prime[MAX]; int pr[MAX]; int num[MAX]; ull f[MAX]; int tot; void init(){ mem(prime,0); tot=0; f[1]=1; for(int i=2; i>t; while(t--){ int n; scanf("%d",&n); int x=n; v.clear(); for(int i=0; i

    推荐阅读


    上一篇：settimeofday

    下一篇：ANDROID|为什么你应该停止使用EventBus