LCM Cardinality 暴力

LCM Cardinality
Time
Limit:
3000MS     Memory
Limit:
0KB     64bit IO
Format:
%lld & %llu

Submit Status

Description

Problem F
LCM
Cardinality

Input: Standard Input

Output: Standard Output

Time Limit: 2 Seconds

A pair of numbers has a unique LCM but a single
number can be the LCM of more than one possible
pairs. For example 12 is
the LCMof (1, 12)(2,
12)
(3,4) etc. For a given positive
integer N, the number of different integer pairs
with LCM is equal to N can
be called theLCM cardinality of that
number N. In this problem your job is to find out
the LCM cardinality of a number.

Input

The input file contains at most 101 lines of inputs. Each line
contains an integer N (0<N<=2*109). Input is terminated by
a line containing a single zero. This line should not be processed.

Output


For each line of input except the last one produce one line of output. This
line contains two
integers N and C.
Here N is the input number
and C is its cardinality. These two numbers are
separated by a single space.

Sample
Input                             Output
for Sample Input






2 
12 
24 
101101291 
0 

2 2

12 8

24 11

101101291 5

 1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 #include<math.h>
5 #include<iostream>
6 #include<algorithm>
7 using namespace std;
8 int gcd(int x,int y)
9 {
10 if(y==0)return x;
11 return gcd(y,x%y);
12 }
13 int lcm(int x,int y)
14 {
15 return x/gcd(x,y)*y;
16 }
17 long long c[500];
18 int main()
19 {
20 int n,nu,i,j,size,ans;
21 while(scanf("%d",&n),n)
22 {
23 ans=nu=0;
24 size=sqrt(n+0.5);
25 for(i=1; i<=size; i++)
26 {
27 if(n%i==0)
28 {
29 c[nu++]=i;
30 if(i*i!=n)
31 c[nu++]=n/i;
32 }
33 }
34 for(i=0; i<nu; i++)
35 {
36 for(j=i; j<nu; j++)
37 if(lcm(c[i],c[j])==n)ans++;
38 }
39 cout<<n<<" "<<ans<<endl;
40 }
41 }

LCM Cardinality 暴力,码迷,mamicode.com

时间: 07-22

LCM Cardinality 暴力的相关文章

UVA 10892 LCM Cardinality 数学

A pair of numbers has a unique LCM but a single number can be the LCM of more than one possiblepairs. For example 12 is the LCM of (1, 12), (2, 12), (3,4) etc. For a given positive integer N, thenumber of di?erent integer pairs with LCM is equal to N

Uva 10892 LCM Cardinality (数论/暴力)

题意:给出数n,求有多少组A,B的最小公约数为n; 思路:3000ms,直接暴力寻找,找到所有能把n整除的数 pi, 枚举所有pi 代码: #include <iostream> #include <cstdio> #include <vector> #define ll long long using namespace std; ll gcd(ll a,ll b) { if(b==0) return a; else return gcd(b,a%b); } int

UVa 10892 (GCD) LCM Cardinality

我一直相信这道题有十分巧妙的解法的,去搜了好多题解发现有的太过玄妙不能领会. 最简单的就是枚举n的所有约数,然后二重循环找lcm(a, b) = n的个数 1 #include <cstdio> 2 #include <vector> 3 #include <algorithm> 4 using namespace std; 5 6 int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } 7 8 int

UVA 10892 LCM Cardinality

题目链接:UVA-10892 题意为给定一个数n,问有多少组不同的数对<a,b>的lcm等于n.看了AC,∑ndless的题解,直接摘抄了. 代码: 1 #include"cstdio" 2 #include"iostream" 3 #include"cstring" 4 #include"algorithm" 5 #include"cstdlib" 6 #include"vector

UVA10892 - LCM Cardinality(分解质因子)

题目链接 题意:输入正整数n,统计有多少对正整数a <= b,满足lcm(a, b) = n. 思路:分解质因子,然后直接暴力求出对数 代码: #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; typedef long long ll; const int MA

vijos P1629八 容斥原理

https://vijos.org/p/1629 注意lcm要用LL 先给一个样例 1 2 1 10 思路.其实这题就是问,给定一堆数,要求不能整除其任意一个的数字有多少个. 容辞 + lcm dfs暴力枚举每一位选还是不选,一共n位.00010101010. 然后奇减偶加 #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorit

UVa10892

10892 LCM CardinalityA pair of numbers has a unique LCM but a single number can be the LCM of more than one possiblepairs. For example 12 is the LCM of (1, 12), (2, 12), (3,4) etc. For a given positive integer N, thenumber of different integer pairs

UVA 11076 Add Again 计算对答案的贡献+组合数学

A pair of numbers has a unique LCM but a single number can be the LCM of more than one possiblepairs. For example 12 is the LCM of (1, 12), (2, 12), (3,4) etc. For a given positive integer N, thenumber of di?erent integer pairs with LCM is equal to N

《算法竞赛入门经典——训练指南》第二章题库

UVa特别题库 UVa网站专门为本书设立的分类题库配合,方便读者提交: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=442 注意,下面注有"extra"的习题并没有在书中出现,但在上面的特别题库中有,属于附加习题. 基础练习 (Basic Problems) UVa11388 GCD LCM UVa11889 Benefit UVa10943 How do y