C - Sigma Function(LightOJ 1336)

简介:

传送门
Password: nefu
题目的截图

题目大意:
就是给你一个数 n 让你求<=n的所有 i 的因子的个数加起来是偶数的个数
比如 一个数 6: 6的因子有 1 2 3 6,所以1+2+3+6 = 12是偶数所以
符合条件

解题思路:
其实我刚开始的时候也没有什么思路,就想着将 <= n的数都进行素因子
分解,n = p1^e1 * p2^e2 * … * pk^ek
F(n) = (p1^(e1+1)-1)/(p1-1) * ^ (p2^(e2+1)-1)/(p2-1)… (pk^(ek+1)-1)/(pk-1)
首先保证其中一项有一个偶数,那考虑起来比较麻烦 所以 我们只需要考虑
奇数的情况就行啦,所以假设 这个 n 是一个平方数,那n == P*P,
F(n) == ((P^3)-1)/(p-1) == P^2+P+1,假设 P是奇数 F(n)是奇数
假设P是偶数 F(n)还是奇数 所以,当这个数是平方数的时候是不符合条件
的,同理当时平方数的2倍的时候,也是不行的,因为当n == 2的时候是
奇数 其实这些规律是在先打完表之后才看出来的看出来了 然后再推一遍
其实推完之后代码就几行。。。
上代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;

#define MM(a) memset(a,0,sizeof(a))

typedef long long LL;
typedef unsigned long long ULL;
const int MAXN = 1e6+5;
const int mod = 1000000007;
const double eps = 1e-7;
/**
bool prime[MAXN];
LL p[MAXN];
LL k;
void isprime()
{
    k = 0;
    prime[1] = false;
    memset(prime, true, sizeof(prime));
    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 fac[MAXN/10],num[MAXN/10],cnt;
void Dec_prime(int m)
{
    cnt = 0;
    MM(num);
    for(LL i=0; p[i]*p[i]<=m&&i<k; i++)
    {
        if(m%p[i] == 0)
        {
            fac[cnt] = p[i];
            while(m%p[i]==0)
            {
                num[cnt]++;
                m /= p[i];
            }
            cnt++;
        }
    }
    if(m > 1)
    {
        fac[cnt] = m;
        num[cnt++] = 1;
    }
}
LL Cal(LL a, LL b)
{
    LL ans = 1;
    while(b--)
        ans *= a;
    return ans;
}
LL ret[MAXN/10];
void Init()
{
    for(int i=0; i<MAXN/10; i++)
        ret[i] = 1;
}
**/
int main()
{
    ///isprime();
    int T;
    LL n;
    cin>>T;
    for(int cas=1; cas<=T; cas++)
    {
        cin>>n;
        /**
        Init();
        for(int j=1; j<=100; j++)
        {
            Dec_prime(j);
            for(int i=0; i<cnt; i++)
            {
                ret[j] *= (Cal(fac[i],num[i]+1)-1)/(fac[i]-1);
            }
        }
        LL sum = 0;
        for(int i=1; i<=100; i++)
            if(ret[i] % 2 == 0)
                puts("YES");
            else
                puts("NO");
        **/
        LL ret = 0;
        for(int i=1; (LL)i*i<=n; i++)///去掉 n^2 和 2*n^2
        {
            ret++;
            if(2*(LL)i*i <= n)
                ret++;
        }
        printf("Case %d: %lld\n",cas,n - ret);
    }
    return 0;
}

去掉注释的那几行 只需要看主程序的就行,注释的是辅助理解的,是为了打表做准备的

目录
相关文章
|
Windows
gitlab 账号注册及修改资料
填写注册信息 点击注册链接奇迹 GitLab后,可以看到以下界面,输入用户名、邮箱等信息,点击 SIGN UP 进行注册: 确认邮件 注册后邮箱会收到一封确认邮件,如果没有收到邮件,可能是被误判为垃圾邮件,请进入邮箱的垃圾箱进行查找。
12160 0
|
1月前
|
人工智能 编解码 物联网
ComfyUI 本地部署 AI 漫剧:8G 显存硬件适配、模型选型与流水线落地实战
本文专为RTX3060/4050等8G显存设备定制,详解4套实测可用的ComfyUI漫剧工作流,涵盖SDXL分镜、LTX图生视频、关键帧长镜头及动作迁移方案,并提供显存优化、离线部署与批量渲染完整实践指南。(239字)
|
4月前
|
弹性计算 Ubuntu Linux
阿里云Linux云服务器搭建Apache:从零开始的完整部署与优化指南
本文提供了一份完整的阿里云Linux云服务器搭建Apache Web服务器的技术指南。首先介绍ECS实例的选购与初始化,重点讲解安全组规则配置,开放22、80、443等必要端口。然后详细演示通过SSH连接服务器,使用yum/dnf包管理器安装Apache及常用模块,并通过systemctl管理服务。接着深入讲解Apache核心配置文件httpd.conf的关键参数,包括ServerName、DocumentRoot、DirectoryIndex等,并详细演示基于域名的虚拟主机配置方法。在性能优化方面,系统讲解KeepAlive长连接调优、MPM多处理模块的选择与参数设置(prefork与eve
|
7月前
|
人工智能 Anolis
倒计时 1 天!欢迎解锁 AI Infra MeetUp 直播渠道,明天北京见
AI Infra 产学研用全链路最新技术趋势与产业动态。
|
7月前
|
XML 数据采集 人工智能
2026 技术向:AI 对话转 Word 的格式问题与工具实测对比
本文是AI技术文档工程师的实战经验总结,直击ChatGPT/DeepSeek/Claude生成内容转Word的三大痛点:LaTeX公式失真、Mermaid图表丢失、代码块无高亮。硬核对比Pandoc、Typora、aitoword、Quarto四大工具在公式转换、Mermaid渲染、样式控制与批量能力上的真实表现,并附决策树与实测耗时数据,助你10分钟选对方案。
|
10月前
|
Linux 虚拟化 iOS开发
UTM 5.0.1 发布 - 基于 QEMU 的 macOS 虚拟机与模拟器应用
UTM 5.0.1 发布 - 基于 QEMU 的 macOS 虚拟机与模拟器应用
1193 2
UTM 5.0.1 发布 - 基于 QEMU 的 macOS 虚拟机与模拟器应用
|
存储 关系型数据库 MySQL
深入MySQL:事务日志redo log详解与实践
【8月更文挑战第24天】在MySQL的InnoDB存储引擎中,为确保事务的持久性和数据一致性,采用了redo log(重做日志)机制。redo log记录了所有数据修改,在系统崩溃后可通过它恢复未完成的事务。它由内存中的redo log buffer和磁盘上的redo log file组成。事务修改先写入buffer,再异步刷新至磁盘,最后提交事务。若系统崩溃,InnoDB通过redo log重放已提交事务并利用undo log回滚未提交事务,确保数据完整。理解redo log工作流程有助于优化数据库性能和确保数据安全。
1541 0
|
存储 传感器 机器学习/深度学习
树莓派踩坑备忘录 --使用Linux
树莓派踩坑备忘录 --使用Linux
766 0
树莓派踩坑备忘录 --使用Linux
|
存储 网络协议 程序员
【TCP 协议】报文格式,数据可靠传输的机制(一)
【TCP 协议】报文格式,数据可靠传输的机制(一)
1588 0
|
存储 缓存 NoSQL
轻松突破文件IO瓶颈:内存映射mmap技术
轻松突破文件IO瓶颈:内存映射mmap技术