LightOJ 1341 - Aladdin and the Flying Carpet

简介:

1341 - Aladdin and the Flying Carpet
Time Limit: 3 second(s) Memory Limit: 32 MB

It's said that Aladdin had to solve seven mysteries before getting the Magical Lamp which summons a powerful Genie. Here we are concerned about the first mystery.

Aladdin was about to enter to a magical cave, led by the evil sorcerer who disguised himself as Aladdin's uncle, found a strange magical flying carpet at the entrance. There were some strange creatures guarding the entrance of the cave. Aladdin could run, but he knew that there was a high chance of getting caught. So, he decided to use the magical flying carpet. The carpet was rectangular shaped, but not square shaped. Aladdin took the carpet and with the help of it he passed the entrance.

Now you are given the area of the carpet and the length of the minimum possible side of the carpet, your task is to find how many types of carpets are possible. For example, the area of the carpet 12, and the minimum possible side of the carpet is 2, then there can be two types of carpets and their sides are: {2, 6} and {3, 4}.

Input

Input starts with an integer T (≤ 4000), denoting the number of test cases.

Each case starts with a line containing two integers: a b (1 ≤ b ≤ a ≤ 1012) where a denotes the area of the carpet and b denotes the minimum possible side of the carpet.

Output

For each case, print the case number and the number of possible carpets.

Sample Input

Output for Sample Input

2

10 2

12 2

Case 1: 1

Case 2: 2

 


题目大意:
给定T组数据,每组数据有两个数 面积s 和 矩形的宽 a,让你求的是在面积s一定的情况下,假设长和宽分别为a 和 b,最小的边长 >= a的有几种方式可以组成矩形(不是正方形)

解析一下样例:
面积为12 ,最小的边长为2:
首先将12进行素因子分解12 = 2^2*3,所以我们能够得到 
12 = 1 * 12(不符合条件 最小的边长<2)
12 = 2 * 6(符合)
12 = 3 * 4(符合)
所以有 2 种方式,输出 2


解题思路:
每次做题的时候先要考虑一下能不能暴力(暴力简单),这个题如果我们要暴力的话肯定会超时,所以就不要暴力了
通过上述的样例分析,我们也知道了我们首先要做的就是将 面积 s 进行素因子分解,这就用到了唯一分解定理,
s = p1^e1 * p2^e2 *……* pk^ek,我们要得到的是因子的个数,这里所说的因子个数默认为正的,得到因子个数的方法是 num = (e1+1) * (e2+1) * ... *(ek+1),然后又因为没有正方形,而且我们要得到的是有多少对,所以将 num除以2,就得到了可以组成矩形面积为 s 的矩形个数,然后我们只需要在 [1,a)的区间内(注意区间开闭)将 s 的因子减掉就行了(num--),这样就可以了。

上代码:
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long LL;
const int MAXN = 1e6+5;
bool prime[MAXN];
LL p[MAXN],k;
void isprime()
{
    memset(prime, true, sizeof(prime));
    prime[1] = false;
    k = 0;
    for(LL i=2; i<MAXN; i++)
    {
        if(prime[i])
        {
            p[k++] = i;
            for(LL j=i*i; j<MAXN; j+=i)
                prime[j] = false;
        }
    }
}

LL Solve(LL m)
{
    LL ret = 1;
    for(LL i=0; p[i]*p[i]<=m&&i<k; i++)
    {
        LL cnt = 0;
        if(m%p[i] == 0)
        {
            while(m%p[i] == 0)
            {
                cnt++;
                m /= p[i];
            }
            ret *= (cnt+1);
        }
    }
    if(m > 1)
        ret *= 2;
    return ret;
}
int main()
{
    isprime();
    int T;
    cin>>T;
    for(int cas=1; cas<=T; cas++)
    {
        LL s,a;
        cin>>s>>a;
        if(a*a >= s)
            printf("Case %d: 0\n",cas);
        else
        {
            LL ret = Solve(s);
            ret /= 2;
            for(LL i=1; i<a; i++)
                if(s % i == 0)
                    ret--;
            printf("Case %d: %lld\n",cas,ret);
        }
    }
    return 0;
}



目录
相关文章
|
关系型数据库 定位技术 数据库
|
Java 测试技术 开发工具
听说你还不会Spring 5.2.x 源码本地环境搭建?
听说你还不会Spring 5.2.x 源码本地环境搭建?
125 0
听说你还不会Spring 5.2.x 源码本地环境搭建?
【STM32 .Net MF开发板学习-14】红外遥控器编码识别
.NET Micro Framework开发板如何获取红外遥控信息,下一篇文章将介绍用遥控器驱动智能小车相关实现细节。
718 0
|
数据库
使用oledbdatareader取得数据库中数据
使用oledbdatareader取得数据库上的数据的时候,要判断一下是数据库中这个值是否是空值,如果是空值出引发一个异常 int iename = myReader.GetOrdinal("ename"); int iurls = myReader.GetOrdinal("urls"); int iquyu = myReader.G
874 0
|
前端开发
当内容超出最大的长度的时候,使用CSS使文本显示省略号
.description{  height:17px;  overflow:hidden;  text-overflow:ellipsis;  -webkit-text-overflow:ellipsis;  -o-text-overflow:ellipsis;  white-space:nowrap; }
1160 0
|
4天前
|
弹性计算 双11 开发者
阿里云ECS“99套餐”再升级!双11一站式满足全年算力需求
11月1日,阿里云弹性计算ECS双11活动全面开启,在延续火爆的云服务器“99套餐”外,CPU、GPU及容器等算力产品均迎来了全年最低价。同时,阿里云全新推出简捷版控制台ECS Lite及专属宝塔面板,大幅降低企业和开发者使用ECS云服务器门槛。
|
21天前
|
存储 弹性计算 人工智能
阿里云弹性计算_通用计算专场精华概览 | 2024云栖大会回顾
阿里云弹性计算产品线、存储产品线产品负责人Alex Chen(陈起鲲)及团队内多位专家,和中国电子技术标准化研究院云计算标准负责人陈行、北京望石智慧科技有限公司首席架构师王晓满两位嘉宾,一同带来了题为《通用计算新品发布与行业实践》的专场Session。本次专场内容包括阿里云弹性计算全新发布的产品家族、阿里云第 9 代 ECS 企业级实例、CIPU 2.0技术解读、E-HPC+超算融合、倚天云原生算力解析等内容,并发布了国内首个云超算国家标准。
阿里云弹性计算_通用计算专场精华概览 | 2024云栖大会回顾
|
3天前
|
人工智能 弹性计算 文字识别
基于阿里云文档智能和RAG快速构建企业"第二大脑"
在数字化转型的背景下,企业面临海量文档管理的挑战。传统的文档管理方式效率低下,难以满足业务需求。阿里云推出的文档智能(Document Mind)与检索增强生成(RAG)技术,通过自动化解析和智能检索,极大地提升了文档管理的效率和信息利用的价值。本文介绍了如何利用阿里云的解决方案,快速构建企业专属的“第二大脑”,助力企业在竞争中占据优势。
|
1天前
|
人工智能 自然语言处理 安全
创新不设限,灵码赋新能:通义灵码新功能深度评测
自从2023年通义灵码发布以来,这款基于阿里云通义大模型的AI编码助手迅速成为开发者心中的“明星产品”。它不仅为个人开发者提供强大支持,还帮助企业团队提升研发效率,推动软件开发行业的创新发展。本文将深入探讨通义灵码最新版本的三大新功能:@workspace、@terminal 和 #team docs,分享这些功能如何在实际工作中提高效率的具体案例。
|
8天前
|
负载均衡 算法 网络安全
阿里云WoSign SSL证书申请指南_沃通SSL技术文档
阿里云平台WoSign品牌SSL证书是由阿里云合作伙伴沃通CA提供,上线阿里云平台以来,成为阿里云平台热销的国产品牌证书产品,用户在阿里云平台https://www.aliyun.com/product/cas 可直接下单购买WoSign SSL证书,快捷部署到阿里云产品中。
1851 6
阿里云WoSign SSL证书申请指南_沃通SSL技术文档