POJ 2480 积性函数 欧拉函数
scturtle
posted @ 2010年7月19日 01:41
in algorithm
, 4644 阅读
因为有性质
当
时
所以gcd是积性函数
因为积性函数的和函数也是积性函数(《初等数论及其应用》P182),所以所求函数
是积性函数
问题简化到素数阶段,须求
,此时用到欧拉公式.因为有
(易见因为
代表的是从1到N中和N最大公约数gcd为d的数的个数)
所以
,又因为
则可求出
#include <iostream>
#include <cstdio>
using namespace std;
typedef unsigned long long u64;
#define maxn 50000
u64 primet[maxn];
int pnum = 0;
void getprimtable()//筛法求出素数
{
bool flag[maxn] = {false};
for (long i = 2; i < maxn; i++)
{
if (!flag[i])
{
primet[pnum++] = i;
for (long j = i + i; j < maxn; j += i) flag[j] = true;
}
}
}
u64 eularpk(u64 p, int k)//欧拉求p^k
{
if (k == 0) return 1;
u64 ans = p - 1;
while (--k)
{
ans *= p;
}
return ans;
}
u64 fpk(u64 p, int k)//求f(p^k)
{
u64 ans = 0, t = 1;
for (int i = 0; i <= k; i++)
{
ans += t * eularpk(p, k - i);
t *= p;
}
return ans;
}
u64 f(u64 n)//求f 因式分解
{
u64 sum = 1;
int p, k;
for (int i = 0; primet[i]*primet[i] <= n; i++)
{
p = primet[i];
//cout<<p<<ends;
if (n % p == 0)
{
k = 0;
while (n % p == 0) {n /= p; k++;}
sum *= fpk(p, k);
}
}
if (n > 1) sum *= fpk(n, 1); // 分解到最后剩下一个素因子
return sum;
}
int main()
{
//freopen("in.txt", "r", stdin);
getprimtable();
u64 n;
while (cin >> n)
{
cout << f(n) << endl;
}
}
2023年12月12日 03:17
Header tags, the signposts of your content's structure, are a crucial element in the labyrinth of 구글 seo, ensuring your message is heard loud and clear.
2023年12月14日 20:19
The convenience of부천출장마사지is unbeatable. A fantastic experience every time.
2023年12月16日 18:11
출장샵 services offer a personalized escape from the daily grind. Discover your oasis of relaxation.
2023年12月17日 22:45
Discover Daegu's late-night wonders with 대밤, your indispensable guide to the city's thriving nightlife scene.
2023年12月20日 00:44
Some times its a pain in the ass to read what website owners wrote but this site is real user friendly ! . 유튜브 프리미엄 무료보기
2023年12月25日 22:00
무료스포츠중계's user-friendly platform makes it a go-to for sports enthusiasts.
2023年12月27日 20:33
For a stress-free experience, use 오피스타 to find nearby massage parlors. Highly recommended!
2023年12月28日 22:34
Unwinding at 진주휴게텔 is a delight. The skilled therapists and variety of massages ensure a peaceful escape from the daily hustle and bustle. My top choice!
2023年12月31日 22:14
누누티비 최신's subtitles are a lifesaver for non-Korean speakers like me.
2024年1月02日 17:14
Pavzi.com provides all the news about Gadgets, the Economy, Technology, Business, Finance and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us. pavzi.com Our site is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.
2024年1月02日 17:16
JNANABHUMI AP provides all latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources full information on each topic which can be accessed through Internet. To ensure that every readers get’s what important and worthy about the topic they search and link to hear from us. jnanabhumiap.in Jnanabhumi AP is a startup by passionate webmasters and bloggers who have passion to provide engaging content which is accurate, interesting and worthy to read. We are mope like a web community where you can find different information’s, resources, topics on day to day incidents or news. We provide you the finest of web content on each and every topics possible with help of editorial and content team.