【打表】ccpc 2022威海 G

亦凉 2024-03-22 23:38 31阅读 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 条评论，31人围观）

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

相关阅读

相关【打表】ccpc 2022威海 G

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

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

相关【期望+状压DP】 2021 CCPC G

[Problem - G - Codeforces][] 题意： ![dca96a9702b54c1590f9e441a4f72d6e.png][] ![5d06c9b7

红太狼/ 2024年03月01日 07:47/ 0 赞/ 30 阅读

相关【反悔贪心】2022ICPC南京 G

[Problem - G - Codeforces][] 题意 ![d90998478af246c99ef1811cc2a9b959.png][] 思路首先容易发现，

港控/mmm°/ 2024年02月21日 11:58/ 0 赞/ 44 阅读

相关 2022CCPC绵阳 ACGHM

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

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

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

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

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

相关 2022 China Collegiate Programming Contest (CCPC) Guangzhou Onsite

L. Station of Fate ![741f41074eef4fe9a518714d73a01463.png][] 求组合数，考虑先分配再排列 incl

向右看齐/ 2024年02月05日 11:56/ 0 赞/ 42 阅读

相关 2019 ccpc 秦皇岛

D 如果1/n是有限小数，不停乘以10，一定在有限次之后成为一个整数。 10的质因子只有2和5，只要保证分母的质因子只有2和5即可 include <iost

柔情只为你懂/ 2023年06月03日 02:53/ 0 赞/ 3 阅读

相关素数打表

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

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

相关打表法

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

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

相关 CCPC比赛信息

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

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