首页 > 代码库 > bestcode#6—1003 HDU 4983 Goffi and GCD 【欧拉函数】
bestcode#6—1003 HDU 4983 Goffi and GCD 【欧拉函数】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4983
题目大意：给出n和k，求出满足条件
的a和b。
首先可以得到的是gcd（n，x）< n 的，所以当k大于2时是无解的，当k等于2时，a=n，b=n才能得到n^2，只有一组。
主要是n=1的情况。
最开始做这个题目的时候是这样想的。先把一个数分为质因数的形式。
/*=========================================
质因数分解
给一个正整数，将N分解质因数(N不大)
输入：n
输出： tot 不同质因数个数
a[] 表示第i个质因数的值
b[] 表示第i个质因数的个数
复杂度：O(sqrt(N))
=========================================*/
#define maxn 1111
int a[maxn], b[maxn], tot = 0;
void factor(int n, int a[], int b[], int &tot) {
int tmp, now;
tmp = (int)(sqrt(n) + 1);
tot = 0;
now = n;
for (int i = 2; i <= tmp; i++) if (now % i == 0) {
a[tot] = i, b[tot] = 0;
while(now % i == 0) {
b[tot]++;
now /= i;
}
tot++;
}
if (now != 1) a[tot] = now, b[tot++] = 1;
}
比如：800 可以分为 2^5 * 5^2 ，根据得到的质因子可以得出其约数：
| 1 | 800 |
| 2 | 400 |
| 4 | 200 |
| 8 | 100 |
| 16 | 50 |
| 32 | 25 |
| 5 | 160 |
| 10 | 80 |
| 20 | 40 |
| 40 | 20 |
| 80 | 10 |
| 160 | 5 |
| 25 | 32 |
| 50 | 16 |
| 100 | 8 |
| 200 | 4 |
| 400 | 2 |
| 800 | 1 |
对于每一个约数来说：比如在1~800中与800公约数为2的约数的个数是：euler（800/2=400）个，
比如这一组：5*160=800 在1~800中与800的公约数为5的个数为euler（800/5=160）个，在1~800中与800的公约数为160的个数为euler（800/160=5）个。
所以在5*160这一组中一共的个数为：erler（5）*euler（160）个。
然后遇见了问题，找出了其质因数后不知道怎么找出所有的约数，然后没有做出来，后来看题解其实发现可以直接暴力的，sqrt（n）的复杂度。时间上是可以过的。
还有一点要注意的是要特判n是否等于1。如果n等于1，则直接输出1 。
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<string.h>
#define LL long long
using namespace std;
LL n,k;
LL euler(LL x) {
LL res = x;
for (LL i = 2; i <= x / i; i++) if (x % i == 0) {
res = res / i * (i - 1);
while(x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
const LL mod=1000000007;
int main()
{
while(scanf("%I64d%I64d",&n,&k)!=EOF)
{
if(n==1) {printf("1\n"); continue;}
if(k>2) {printf("0\n"); continue;}
if(k==2) {printf("1\n"); continue;}
else
{
LL ans=0;
for(LL i=1;i*i<=n;++i)
{
if(n%i==0)
{
LL x=n/i;
if(i*i==n) ans+=euler(x)*euler(i);
else ans+=euler(x)*euler(i)*2;
ans%=mod;
}
}
printf("%I64d\n",ans);
}
}
return 0;
}
本来想直接打表1000000000/2的表，发现太大了打不了...... 后来看题解发现了一个人用的map打的表，想想还是很屌的，时间复杂度缩短了一半。
map<int,int> mp;
int phi(int n)
{
int i,mul,nn;
if (n==1) return 1;
if (mp.find(n)!=mp.end()) return mp[n];
for (i=2;i*i<=n;i++)
if (n%i==0)
{
nn=n;
nn/=i;
mul=(i-1);
while (nn%i==0)
{
nn/=i;
mul*=i;
}
mp[n]=phi(nn)*mul;
return phi(nn)*mul;
}
mp[n]=n-1;
return n-1;
}
注意在main函数里面要有一个操作：
mp.clear();
bestcode#6—1003 HDU 4983 Goffi and GCD 【欧拉函数】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。