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(数论)的更多相关文章
-
hdu 4983 Goffi and GCD(数论)
题目链接:hdu 4983 Goffi and GCD 题目大意:求有多少对元组满足题目中的公式. 解题思路: n = 1或者k=2时:答案为1 k > 2时:答案为0(n≠1) k = 1时: ...
-
hdu 4983 Goffi and GCD(欧拉函数)
Problem Description Goffi is doing his math homework and he finds an equality on his text book: gcd( ...
-
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 ...
-
【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不为 ...
-
HDU 4981 Goffi and Median(水)
HDU 4981 Goffi and Median 思路:排序就能够得到中间数.然后总和和中间数*n比較一下就可以 代码: #include <cstdio> #include <c ...
-
HDU 4982 Goffi and Squary Partition(推理)
HDU 4982 Goffi and Squary Partition 思路:直接从全然平方数往下找,然后推断是否能构造出该全然平方数,假设能够就是yes,假设都不行就是no.注意构造时候的推断,因为 ...
-
hdu 5869 区间不同GCD个数(树状数组)
Different GCD Subarray Query Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K ( ...
-
hdu 5656 CA Loves GCD(n个任选k个的最大公约数和)
CA Loves GCD Accepts: 64 Submissions: 535 Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 2 ...
-
Bash and a Tough Math Puzzle CodeForces 914D 线段树+gcd数论
Bash and a Tough Math Puzzle CodeForces 914D 线段树+gcd数论 题意 给你一段数,然后小明去猜某一区间内的gcd,这里不一定是准确值,如果在这个区间内改变 ...
随机推荐
-
Android的学习第六章(布局二--RelativeLayout)
今天我们来说一下Android布局中的Relativelayout布局(相对布局) 根据英译过来意思是相对布局,很容易理解,这一样布局使用的是元素与元素之间的微调做到布局的 含义:通过元素与元素之间的 ...
-
Datastage数据装载报错:Consumed more than 1000000 bytes looking for record delimiter
使用Datastage装载数据时报错如下图: 使用ds进行数据传输时,出现上述问题,最终找到了问题的原因: 我所使用的数据文件比较大,上传到服务器的时候传了80%就出现服务器存储空间不够,我删除以前的 ...
-
Python教程:操作数据库,MySql的安装详解
各位志同道合的同仁请点击上方关注 本教程是基于Python语言的深入学习.本次主要介绍MySql数据库软件的安装.不限制语言语法,对MySql数据库安装有疑惑的各位同仁都可以查看一下. 如想查看学习P ...
-
为什么用IP无法访问网站,域名可以访问?
我们访问网站都是通过域名进行访问的,偶尔会使用网站IP进行访问,如学校通常使用IP登录教务处,但很多的时候我们无法通过ip进行访问其他网站,这就涉及到服务器的问题了. 网站都是依托在服务器上面的,而服 ...
-
FatMouse and Cheese
FatMouse and Cheese Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u ...
-
关于事件mouseover ,mouseout ,mouseenter,mouseleave的区别
轮播中大多会选择mouseover和mouseout 这个时候是没有任何问题的 但当遇到有css3动画的时候,会发现移入移出过快 动画还没加载完成就需要执行下一个动画,完了动画样式就错乱了. 这时候 ...
-
html<;meta>;标签
1. 定义说明 <meta>提供与页面有关的元数据,元数据是对数据的描述 <meta>总是位于<head></head>中 <meta>定义 ...
-
Matlab如何循环读取文件
循环读取图片第一种方法①List =dir('*.jpg'); %如需其它图片格式支持,可以自己[重载dir()]函数,实现查找所有图片文件的功能,%如果图片是其它路径,可以用 ["路径&q ...
-
mac版win10装eclipse图标太小了,解决办法(2k显示屏+win10)
安装了Eclipse并且打开之后,发现图标显示极其细小,肉眼几乎无法看清了.这是由于Eclipse对高分屏没有作适配导致的. Windows 10本身对于高分屏的支持已是相当不错,苏菲4的屏幕分辨率为 ...
-
JS实现一个基于对象的链表
JS实现一个基于对象的链表 /*JS实现一个基于对象的链表*/ function Node(element){ this.element = element;//节点存储的元素 this.next = ...