【二分/双指针】ABC250 D - 250-like Number

深碍√TFBOYSˉ_ 2024-03-23 11:35 34阅读 0赞

[D - 250-like Number (atcoder.jp)][D - 250-like Number _atcoder.jp]

题意：

![9ef9c6e12b1649fb860f9ba87b4a0d91.png][]

![75a41144ad4c4939baf1927cc6877612.png][]

思路：

把质数筛出来之后

枚举p的位置，双指针q的位置即可

Code：

#include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int Inf=1e18;
    
    map<int,int> mp;
    int N,len=0,ans=0;
    int prime[mxn],vis[mxn];
    void p_init(int n){
        for(int i=2;i<=n;i++){
            if(!vis[i]) prime[++len]=i;
            for(int j=1;i<=n/prime[j];j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
    }
    int F(int x,int y){
        if(x*y*y*y>4e18) return 4e18;
        return x*y*y*y;
    }
    void solve(){
        cin>>N;
        int r=len;
        int ans=0;
        for(int l=1;l<=len;l++){
            while(l<=r&&F(prime[l],prime[r])>N) r--;
            if(l>r) break;
            ans+=(r-l);
        }
        cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
        p_init(1e6);
    	while(__--)solve();return 0;
    }

[D - 250-like Number _atcoder.jp]: https://atcoder.jp/contests/abc250/tasks/abc250_d
[9ef9c6e12b1649fb860f9ba87b4a0d91.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/90ef25a41542493a83b94718139e1a1b.png
[75a41144ad4c4939baf1927cc6877612.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/24c27e16948f4983afb03336cf578979.png

发表评论取消回复

表情：

评论列表（有 0 条评论，34人围观）

还没有评论，来说两句吧...

相关阅读

相关【二分/双指针】ABC250 D - 250-like Number

[D - 250-like Number (atcoder.jp)][D - 250-like Number _atcoder.jp] 题意： ![9ef9c6e12b16

深碍√TFBOYSˉ_/ 2024年03月23日 11:35/ 0 赞/ 35 阅读

相关【双指针】ABC229 D - Longest X

感觉这道题很简单啊，应该想彻底了再看题解的.... [D - Longest X (atcoder.jp)][D - Longest X _atcoder.jp] 题意：

蔚落/ 2024年03月22日 11:02/ 0 赞/ 28 阅读

相关【二维属性+贪心+双指针】ABC 195 D

[D - Shipping Center (atcoder.jp)][D - Shipping Center _atcoder.jp] 题意： ![86fab8a4ccff

绝地灬酷狼/ 2024年03月17日 15:40/ 0 赞/ 42 阅读

相关【贪心+双指针】ABC308 F

[F - Vouchers (atcoder.jp)][F - Vouchers _atcoder.jp] 题意： ![b9d9dfba42284ccb967e5089f6

r囧r小猫/ 2024年03月17日 13:55/ 0 赞/ 61 阅读

相关 cha250更改域名

计算机怎么修改域名 1、首先右键单击计算机，此时会弹出一个菜单选择对zhidao话框，在此菜单选择对话框里点击最后一个选项【属性】，将其打开。 2、此时页面会切换到系统

偏执的太偏执、/ 2023年09月26日 13:51/ 0 赞/ 4 阅读

相关豆瓣图书Top250

从豆瓣图书Top250抓取数据，并通过词云图展示导入库 from lxml import etree 解析库 import time 时间 imp

男娘i/ 2023年08月17日 16:32/ 0 赞/ 58 阅读

相关 250.火焰特效

效果 (源码网盘地址在最后) ![16ff17e1ef94296bb222f6d087d4197c.gif][] 源码 index.html <!DOC

￡神魔★判官ぃ/ 2022年08月28日 07:58/ 0 赞/ 108 阅读

相关 uestc 250 windy数【数位dp】

题目：[uestc 250 windy数][uestc 250 windy] 题意： windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的

迈不过友情╰/ 2022年08月13日 13:37/ 0 赞/ 158 阅读

相关 L1-041. 寻找250

![oc_oo9ypsem8x5.jpg][] 对方不想和你说话，并向你扔了一串数…… 而你必须从这一串数字中找到“250”这个高大上的感人数字。输入格式：输入在一行

阳光穿透心脏的1/2处/ 2022年05月25日 02:50/ 0 赞/ 138 阅读

相关豆瓣电影Top250——电影详细

闲得无聊去爬了一下豆瓣的Top250电影信息代码如下，直接可以运行， import requests from lxml import etree

￡神魔★判官ぃ/ 2022年02月25日 04:47/ 0 赞/ 387 阅读