【打表】ccpc 2022威海 G

亦凉 2024-03-22 23:38 10阅读 0赞

[Problem - G - Codeforces][]

题意：

![1aeaeb5a639f4c9d903bfdba219568d5.png][]

思路：

这种题大概率只能打表

把gcd(kx^x,x)的值打出来，可以发现是个循环节

![70bd73ac38734a4eaaf78f3e9fc9b277.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    
    int x,N;
    int l,r,t,bk;
    int cnt=0;
    int a[mxn];
    
    int get(int x){
    	int res=0;
    	int b=x/bk;
    	int c=x%bk;
    	return a[bk-1]*b+a[c];
    }
    void solve(){
    	cin>>x>>N;
    	t=__lg(x);
    	while((1ll<<t)<x) t++;
    	bk=(1ll<<t);
    	for(int k=1;k<=bk;k++){
    		if(__gcd((k*x)^x,x)==1ll) a[k]++;
    	}
    	for(int i=2;i<bk;i++) a[i]+=a[i-1];
    	for(int i=1;i<=N;i++){
    		cin>>l>>r;
    		cout<<get(r)-get(l-1)<<'\n';
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - G - Codeforces]: https://codeforces.com/gym/104023/problem/G
[1aeaeb5a639f4c9d903bfdba219568d5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a9069812f6bf48278a4a057bdff65198.png
[70bd73ac38734a4eaaf78f3e9fc9b277.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/89806883425942a2aa828b665c51a803.png

发表评论取消回复

表情：

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

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

相关阅读

相关【打表】ccpc 2022威海 G

[Problem - G - Codeforces][] 题意： ![1aeaeb5a639f4c9d903bfdba219568d5.png][] 思路：这种题大概

亦凉/ 2024年03月22日 23:38/ 0 赞/ 11 阅读

相关 2022CCPC绵阳 ACGHM

[Dashboard - 2022 China Collegiate Programming Contest (CCPC) Mianyang Onsite - Codeforc

今天药忘吃喽~/ 2024年02月18日 11:32/ 0 赞/ 14 阅读

相关 2023CCPC深圳流水账

在高铁上无聊，写一个这三天的小总结吧不知道该写点啥，就想到什么写什么了铁了，也在意料之中，概率期望和字符串一直是弱点，考前也在赌不会考这两个结果两个都考了，赫赫，看来在

傷城~/ 2024年02月18日 09:42/ 0 赞/ 11 阅读

相关 2022 China Collegiate Programming Contest (CCPC) Guilin Site

A.Lily [Problem - A - Codeforces][] 题意 ![67b42e3098944de79be6bba455d7bc29.png][] 思

今天药忘吃喽~/ 2024年02月17日 12:48/ 0 赞/ 7 阅读

相关 CCPC2019网络赛

1001：输出A&B 特判A&B=0 1007: 思路：按照题意去写，分为四个部分，只有第三部分与第一部分相反，其余都与第一部分相同所以我们以第一部分为基准，去扩

深藏阁楼爱情的钟/ 2023年08月17日 16:26/ 0 赞/ 97 阅读

相关 N皇后（打表）

![Center][] ![Center 1][] [Center]: /images/20220610/4b54052db2ce46799ae4f302a1ae7

我会带着你远行/ 2022年06月10日 02:21/ 0 赞/ 118 阅读

相关素数打表

我们经常会使用到素数打表这个工具，判断方法是多种多样的，下面我列举一种好理解的判断方法思路： 1、初始化visit数组，初始化为true,用visit\[i\]=tr

阳光穿透心脏的1/2处/ 2022年05月30日 05:56/ 0 赞/ 260 阅读

相关打表-(POJ)机器翻译

打表-(POJ)机器翻译 -------------------- 题目链接：[机器翻译][Link 1] 思路看了下题目数据的范围，百万级，如果

╰+哭是因爲堅強的太久メ/ 2022年05月18日 06:53/ 0 赞/ 151 阅读

相关打表法

\include<iostream> \include<stdio.h> \include<math.h> using namespace std; bool z

朴灿烈づ我的快乐病毒、/ 2022年02月27日 05:24/ 0 赞/ 164 阅读

相关 CCPC比赛信息

去CCPC的官网查看 [CCPC][] ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG

你的名字/ 2022年02月23日 01:44/ 0 赞/ 179 阅读