LightOJ 1236 Pairs Forming LCM

2024-05-12 19:32
文章标签 lightoj lcm 1236 pairs forming

本文主要是介绍LightOJ 1236 Pairs Forming LCM,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一道唯一分解的题目。

代码:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;#define maxn 10000010
typedef long long LL;LL prime[1000000];
bool p[maxn];
int k;
void find_prim()
{k = 0;for(LL i = 2; i <= maxn; i++){if(!p[i]){prime[k++] = i;for(LL j = i+i; j <= maxn; j+=i){p[j] = 1;}}}
}
int main()
{find_prim();int t, kase = 1; cin >> t;LL n;while(t--){scanf("%lld", &n);LL ans = 1;for(int i = 0; i < k && (LL)prime[i]*prime[i] <= n; i++){if(n%prime[i] == 0){int cnt = 0;while(n%prime[i] == 0){cnt++;n /= prime[i];}ans *= (2*cnt + 1);}}if(n > 1) ans *= 3;ans = ans/2 + 1;printf("Case %d: %lld\n", kase++, ans);}return 0;
}



这篇关于LightOJ 1236 Pairs Forming LCM的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/983539

相关文章

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

[置顶]LCM性质 + 组合数 - HDU 5407 CRB and Candies

CRB and Candies Problem's Link  Mean:  给定一个数n,求LCM(C(n,0),C(n,1),C(n,2)...C(n,n))的值,(n<=1e6). analyse: 很有趣的一道数论题! 看了下网上别人的做法,什么Kummer定理我还真没听说过,仔细研究一下那个鬼定理真是涨姿势了! 然而这题我并不是用Kummer那货搞的(w

Codeforces Round #328 (Div. 2)C. The Big Race(数学gcd lcm)

题目连接 题意:比赛时 ,居然理解错题意= =,以为两个人的速度是一样的,然后有个人的只会有一步是w米,另一个人只有一步是b米。。。。 就是一个人每一步是w,一个人每一步是b,终点后是深渊,然后长度是在1–t随机选择一个d作为赛道长度,问不能区分二人胜负的可能。 思路:就是求d%w==d%b = = #include<bits/stdc++.h>using namespace std;

LightOJ 1068 Investigation (数位dp)

http://www.lightoj.com/volume_showproblem.php?problem=1068 求出区间[A,B]内能被K整除且各位数字之和也能被K整除的数的个数。(1 ≤ A ≤ B < 231 and 0 < K < 10000) 算是最简单的数位dp了,k在这里是10000,三维数组都开不开。但是想想会发现A,B最多有10位,各位数字之和不会超过90,那么当

[ARC050C] LCM 111 题解

一句话题解: 转化两个大数的 gcd ⁡ \gcd gcd ,再用迭代的思想求答案。 [ARC050C] LCM 111 题解 题目 题意 给你 a a a , b b b , m m m ,其中 1 ≤ A , B ≤ 1 0 18 , 2 ≤ M ≤ 1 0 9 1\le A,B\le 10^{18},2\le M\le 10^9 1≤A,B≤1018,2≤M≤109 ,让

【lua实战】lua中pairs和ipairs的区别

很久以前,我在使用lua的过程中,对于pairs和ipairs的理解还处于表层,认为我了解的就是全部。 ipairs就是对表中元素进行顺序排序,pairs就是对表中元素进行随机排序。 比如如下例子: local t = {20, "ss", print, 10}print("------ipairs------")for k,v in ipairs(t) doprint(k,v)end

B. Pleasant Pairs

time limit per test 2 seconds memory limit per test 256 megabytes You are given an array a1,a2,…,ana1,a2,…,an consisting of nn distinct integers. Count the number of pairs of indices (i,j)(i,j) su

Leetcode 3267. Count Almost Equal Pairs II

Leetcode 3267. Count Almost Equal Pairs II 1. 解题思路2. 代码实现 题目链接:3267. Count Almost Equal Pairs II 1. 解题思路 这一题同样是题目3265. Count Almost Equal Pairs I的进阶版本。 它主要的区别在于说: 最大的操作次数增加到两次;数组长度增加到最大5000 然后,首

lightoj 1050 - Marbles (概率DP)

思路:定义dp[i][j] 为 袋子中有i个红球和j个红球时获胜的概率 那么根据题意我只可以任意拿而对手只拿蓝球。那么 dp[i][j] = (拿到红球的概率) * dp[i-1][j-1] + (拿到蓝球的概率) * dp[i][j-2]; 边界:当红球没有时,获胜的概率为1 注意点:T比较大,需要把所有数据预处理出来直接查询,否则超时 /*********************

lightoj 1047 Neighbor House(Dp)

思路:定义dp[i][j] 为粉刷第i个房子用的颜色j dp[i][j] = min(dp[i-1][(j+1)%3] , dp[i-1][(j+2) % 3]); 一共有三种颜色{0, 1, 2},任取一种颜色{j},那么和颜色j不同的颜色就为{(j + 1) % 3 , (j + 2) % 3}; /******************************************