首页 > 代码库 > hdu 4983 Goffi and GCD(数论)
hdu 4983 Goffi and GCD(数论)
题目链接:hdu 4983 Goffi and GCD
题目大意:求有多少对元组满足题目中的公式。
解题思路:
- n = 1或者k=2时:答案为1
- k > 2时:答案为0(n≠1)
- k = 1时:需要计算,枚举n的因子,令因子k=gcd(n?a,n, 那么另一边的gcd(n?b,n)=nk才能满足相乘等n,满足k=gcd(n?a,n)的a的个数即为?(n/s),欧拉有o(n ̄ ̄√的算法
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1e5;
const int MOD = 1e9+7;
typedef long long ll;
ll ans;
int N, K, M;
int np, pri[maxn+5], vis[maxn+5];
int nf, fact[maxn+5], coun[maxn+5];
void prime_table (int n) {
np = 0;
memset(vis, 0, sizeof(vis));
for (int i = 2; i <= n; i++) {
if (vis[i])
continue;
pri[np++] = i;
for (int j = 2 * i; j <= n; j += i)
vis[j] = 1;
}
}
void div_factor(int n) {
nf = 0;
for (int i = 0; i < np; i++) {
if (n % pri[i] == 0) {
coun[nf] = 0;
while (n % pri[i] == 0) {
coun[nf]++;
n /= pri[i];
}
fact[nf++] = pri[i];
}
}
if (n != 1) {
coun[nf] = 1;
fact[nf++] = n;
}
}
int euler_phi(int n) {
int m = (int)sqrt((double)n+0.5);
int ret = n;
for (int i = 2; i <= m; i++) {
if (n % i == 0) {
ret = ret / i * (i-1);
while (n%i==0)
n /= i;
}
}
if (n > 1)
ret = ret / n * (n - 1);
return ret;
}
ll add (int s) {
ll a = euler_phi(N/s);
ll b = euler_phi(s);
ll ret = a * b * 2;
if (s == N / s)
ret /= 2;
return ret;
}
void dfs (int s, int d) {
if (s > M)
return;
if (d == nf) {
ans = (ans + add(s)) % MOD;
return;
}
for (int i = 0; i <= coun[d]; i++) {
dfs(s, d+1);
s *= fact[d];
}
}
int solve () {
ans = 0;
M = (int)sqrt((double)N);
div_factor(N);
dfs (1, 0);
return ans % MOD;
}
int main () {
prime_table(maxn);
while (scanf("%d%d", &N, &K) == 2) {
if (N == 1)
printf("1\n");
else if (K > 2)
printf("0\n");
else if (K == 2)
printf("1\n");
else
printf("%d\n", solve());
}
return 0;
}
hdu 4983 Goffi and GCD(数论)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。