2017百度之星初赛(A):小C的倍数问题

题目链接:HDOJ6108

 假设P进制下有个数(abc)~P~,若这个数满足:(abc)~P~ % B == 0,则以下两个等式一定成立:

  1. (a * P^2^ + b *P^1^ + c * P^0^) % B = sum % B == 0
  2. (a + b + c) % B = ans % B == 0

 以上两个式子同时成立的条件是:P % B == 1,所以满足条件的B的个数为P - 1的因子数

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        while((T--) != 0) {
            int n = cin.nextInt();
            solve(n - 1);
        }
    }
    private static void solve(int x) {
        int ans = 2;
        for(int i = 2;i <= Math.sqrt(x);i++) 
            if(x % i == 0)
                ans += 2;
        if((int)Math.sqrt(x) * (int)Math.sqrt(x) == x) 
            ans--;
        System.out.println(ans);
    }
}

 每个数至少两个因子,一个1,一个本身,所以初始化ans=2,其次,只用遍历到sqrt(x)即可,找到可以除尽的ans就加2,因为每个数的因子都是成对的,最后如果这个数本身就是个完全平方数,那就再减掉一个即可

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-79-单词搜索(用dfs解决)

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

3761
来自专栏chenjx85的技术专栏

leetcode-492-Construct the Rectangle

2155
来自专栏Python爬虫与数据挖掘

浅谈网络爬虫中广度优先算法和代码实现

前几天给大家分享了网络爬虫中深度优先算法的介绍及其代码实现过程,没来得及上车的小伙伴们可以戳这篇文章——浅谈网络爬虫中深度优先算法和简单代码实现。今天小编给大家...

1425
来自专栏ml

二分查找算法基本思想

转载http://www.cppblog.com/converse/archive/2009/10/05/97905.html 二分查找算法基本思想 二分查找算...

50111
来自专栏desperate633

LintCode 数字三角形题目分析1 (常规的动态规划解法)分析2 (如果你只用额外空间复杂度O(n)的条件)

给定一个数字三角形,找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。 ** 注意事项 如果你只用额外空间复杂度O(n)的条件下完成可以获...

962
来自专栏GIS讲堂

Geotools中实现NC转等值面

前面的文章有实现IDW插值并生成等值面的,本文在前文基础上实现气象NC数据生成等值面。

3334
来自专栏Golang语言社区

Go语言 -浮点数

Go提供了两种size的浮点数,float32和float64。它们的算术规范是由IEEE754国际标准定义,现代CPU都实现了这个规范。 浮点数能够表示的范...

3784
来自专栏desperate633

LintCode 寻找旋转排序数组中的最小值题目分析代码

假设一个旋转排序的数组其起始位置是未知的(比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2)。

923
来自专栏编程之旅

堆排序算法

啊噢,又开始写算法学习的笔记了。最近在准备面试的过程中又把这些常见的排序算法拿出来复习复习,既然这篇写到了堆排序,那么就代表堆排序算法的概念被我忘的差不多了,写...

2473
来自专栏WD学习记录

牛客网 和为S的两个数字

输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

1804

扫码关注云+社区

领取腾讯云代金券