This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub tko919/library
#include "Math/powertable.hpp"
#pragma once #include "Math/sieve.hpp" template<typename T>vector<T> powertable(int n,ll k){ //0^k,1^k,..,n^k assert(k>=0); auto ps=sieve(n+1); vector<T> f(n+1,1); if(k)f[0]=0; for(auto& p:ps){ T pk=T(p).pow(k); for(ll q=p;q<=n;q*=p){ for(ll i=q;i<=n;i+=q)f[i]*=pk; } } return f; } /** * @brief Enumrate $n^k$ */
#line 2 "Math/sieve.hpp" template<int L=50101010>vector<int> sieve(int N){ bitset<L> isp; int n,sq=ceil(sqrt(N)); for(int z=1;z<=5;z+=4){ for(int y=z;y<=sq;y+=6){ for(int x=1;x<=sq and (n=4*x*x+y*y)<=N;++x){ isp[n].flip(); } for(int x=y+1;x<=sq and (n=3*x*x-y*y)<=N;x+=2){ isp[n].flip(); } } } for(int z=2;z<=4;z+=2){ for(int y=z;y<=sq;y+=6){ for (int x=1;x<=sq and (n=3*x*x+y*y)<=N;x+=2){ isp[n].flip(); } for(int x=y+1;x<=sq and (n=3*x*x-y*y)<=N;x+=2){ isp[n].flip(); } } } for(int y=3;y<=sq;y+=6){ for(int z=1;z<=2;++z){ for(int x=z;x<=sq and (n=4*x*x+y*y)<=N;x+=3){ isp[n].flip(); } } } for(int n=5;n<=sq;++n)if(isp[n]){ for(int k=n*n;k<=N;k+=n*n){ isp[k]=false; } } isp[2]=isp[3]=true; vector<int> ret; for(int i=2;i<=N;i++)if(isp[i]){ ret.push_back(i); } return ret; } /** * @brief Prime Sieve */ #line 3 "Math/powertable.hpp" template<typename T>vector<T> powertable(int n,ll k){ //0^k,1^k,..,n^k assert(k>=0); auto ps=sieve(n+1); vector<T> f(n+1,1); if(k)f[0]=0; for(auto& p:ps){ T pk=T(p).pow(k); for(ll q=p;q<=n;q*=p){ for(ll i=q;i<=n;i+=q)f[i]*=pk; } } return f; } /** * @brief Enumrate $n^k$ */