HDU 4983 Goffi and GCD(数论)

时间:2022-02-11 01:24:48

HDU 4983 Goffi and GCD

思路:数论题。假设k为2和n为1。那么仅仅可能1种。其它的k > 2就是0种,那么事实上仅仅要考虑k = 1的情况了。k = 1的时候,枚举n的因子,然后等于求该因子满足的个数,那么gcd(x, n) = 该因子的个数为phi(n / 该因子),然后再利用乘法原理计算就可以

代码:

#include <cstdio>
#include <cstring>
#include <cmath> typedef long long ll; const ll MOD = 1000000007;
const int N = 35333; ll n, k, pn, vis[N];
ll prime[N], frc[N], fn, cnt[N]; void getprime() {
pn = 0;
for (ll i = 2; i < N; i++) {
if (vis[i]) continue;
prime[pn++] = i;
for (ll j = i * i; j < N; j += i)
vis[j] = 1;
}
} void getfrc(ll n) {
fn = 0;
for (ll i = 0; i < pn && n >= prime[i]; i++) {
if (n % prime[i] == 0) {
frc[fn] = prime[i];
cnt[fn] = 0;
while (n % prime[i] == 0) {
cnt[fn]++;
n /= prime[i];
}
fn++;
}
}
if (n != 1) {
frc[fn] = n;
cnt[fn++] = 1;
}
} ll ans = 0; ll phi(ll n) {
ll m = (ll)sqrt(n * 1.0);
ll ans = n;
for (ll i = 2; i <= m; i++) {
if (n % i == 0) {
ans = ans / i * (i - 1);
while (n % i == 0) n /= i;
}
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
} void dfs(ll u, ll sum) {
if (u == fn) {
ll r = n / sum;
ans = (phi(n / sum) * phi(sum) % MOD + ans) % MOD;
return;
}
for (ll i = 0; i <= cnt[u]; i++) {
dfs(u + 1, sum);
sum *= frc[u];
}
} ll solve() {
getfrc(n);
ans = 0;
dfs(0, 1);
return ans;
} int main() {
getprime();
while (~scanf("%I64d%I64d", &n, &k)) {
if (n == 1) printf("1\n");
else if (k == 2) printf("1\n");
else if (k > 2) printf("0\n");
else {
printf("%I64d\n", solve());
}
}
return 0;
}

HDU 4983 Goffi and GCD(数论)的更多相关文章

  1. hdu 4983 Goffi and GCD&lpar;数论&rpar;

    题目链接:hdu 4983 Goffi and GCD 题目大意:求有多少对元组满足题目中的公式. 解题思路: n = 1或者k=2时:答案为1 k > 2时:答案为0(n≠1) k = 1时: ...

  2. hdu 4983 Goffi and GCD(欧拉函数)

    Problem Description Goffi is doing his math homework and he finds an equality on his text book: gcd( ...

  3. HDU 4983 Goffi and GCD

    题目大意:给你N和K,问有多少个数对满足gcd(N-A,N)*gcd(N-B,N)=N^K.题解:由于 gcd(a, N) <= N,于是 K>2 都是无解,K=2 只有一个解 A=B=N ...

  4. 【HDOJ】4983 Goffi and GCD

    题意说的非常清楚,即求满足gcd(n-a, n)*gcd(n-b, n) = n^k的(a, b)的不同对数.显然gcd(n-a, n)<=n, gcd(n-b, n)<=n.因此当n不为 ...

  5. HDU 4981 Goffi and Median(水)

    HDU 4981 Goffi and Median 思路:排序就能够得到中间数.然后总和和中间数*n比較一下就可以 代码: #include <cstdio> #include <c ...

  6. HDU 4982 Goffi and Squary Partition(推理)

    HDU 4982 Goffi and Squary Partition 思路:直接从全然平方数往下找,然后推断是否能构造出该全然平方数,假设能够就是yes,假设都不行就是no.注意构造时候的推断,因为 ...

  7. hdu 5869 区间不同GCD个数&lpar;树状数组&rpar;

    Different GCD Subarray Query Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K ( ...

  8. hdu 5656 CA Loves GCD&lpar;n个任选k个的最大公约数和&rpar;

    CA Loves GCD  Accepts: 64  Submissions: 535  Time Limit: 6000/3000 MS (Java/Others)  Memory Limit: 2 ...

  9. Bash and a Tough Math Puzzle CodeForces 914D 线段树&plus;gcd数论

    Bash and a Tough Math Puzzle CodeForces 914D 线段树+gcd数论 题意 给你一段数,然后小明去猜某一区间内的gcd,这里不一定是准确值,如果在这个区间内改变 ...

随机推荐

  1. Android的学习第六章&lpar;布局二--RelativeLayout&rpar;

    今天我们来说一下Android布局中的Relativelayout布局(相对布局) 根据英译过来意思是相对布局,很容易理解,这一样布局使用的是元素与元素之间的微调做到布局的 含义:通过元素与元素之间的 ...

  2. Datastage数据装载报错:Consumed more than 1000000 bytes looking for record delimiter

    使用Datastage装载数据时报错如下图: 使用ds进行数据传输时,出现上述问题,最终找到了问题的原因: 我所使用的数据文件比较大,上传到服务器的时候传了80%就出现服务器存储空间不够,我删除以前的 ...

  3. Python教程:操作数据库,MySql的安装详解

    各位志同道合的同仁请点击上方关注 本教程是基于Python语言的深入学习.本次主要介绍MySql数据库软件的安装.不限制语言语法,对MySql数据库安装有疑惑的各位同仁都可以查看一下. 如想查看学习P ...

  4. 为什么用IP无法访问网站,域名可以访问?

    我们访问网站都是通过域名进行访问的,偶尔会使用网站IP进行访问,如学校通常使用IP登录教务处,但很多的时候我们无法通过ip进行访问其他网站,这就涉及到服务器的问题了. 网站都是依托在服务器上面的,而服 ...

  5. FatMouse and Cheese

    FatMouse and Cheese Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u ...

  6. 关于事件mouseover &comma;mouseout &comma;mouseenter&comma;mouseleave的区别

    轮播中大多会选择mouseover和mouseout  这个时候是没有任何问题的 但当遇到有css3动画的时候,会发现移入移出过快 动画还没加载完成就需要执行下一个动画,完了动画样式就错乱了. 这时候 ...

  7. html&lt&semi;meta&gt&semi;标签

    1. 定义说明 <meta>提供与页面有关的元数据,元数据是对数据的描述 <meta>总是位于<head></head>中 <meta>定义 ...

  8. Matlab如何循环读取文件

    循环读取图片第一种方法①List =dir('*.jpg'); %如需其它图片格式支持,可以自己[重载dir()]函数,实现查找所有图片文件的功能,%如果图片是其它路径,可以用 ["路径&q ...

  9. mac版win10装eclipse图标太小了,解决办法(2k显示屏&plus;win10)

    安装了Eclipse并且打开之后,发现图标显示极其细小,肉眼几乎无法看清了.这是由于Eclipse对高分屏没有作适配导致的. Windows 10本身对于高分屏的支持已是相当不错,苏菲4的屏幕分辨率为 ...

  10. JS实现一个基于对象的链表

    JS实现一个基于对象的链表 /*JS实现一个基于对象的链表*/ function Node(element){ this.element = element;//节点存储的元素 this.next = ...