首页 > 其他分享 >CF1855B Longest Divisors Interval 题解

CF1855B Longest Divisors Interval 题解

时间:2023-07-30 12:22:06浏览次数:46  
标签:val Ty 题解 void Interval char gc 区间 Divisors

题意:

给定一个数 \(n\),求一个连续区间 \([l,r]\) 使得 \(n\) 是区间内每个数的倍数,最大化这个区间的长度(多组数据)。

思路:

逆向思考一波,(

如果一个数 \(x\) 不是 \(n\) 的因数,那么 \(x\) 的倍数不能在区间内。

举个例子,比如 $ n $ 是13,3不是13的因数,\(3,6,9,12\) 也就不可能出现在区间内z,也就是每隔2个数就有一个不能选在区间中。

233

也就是说,一个数 \(x\) 不是 \(n\) 的因数,那么这个区间长度就不可能超过 \(x\),最长也只能到 \(x-1\)。

我们可以找到 \(1,2,3,4,...\) 中第一个不是 \(n\) 的因数的 \(x\) ,易知 \(1,2,3,...,x-1\) 都是符合要求的数。

既然最长只能到 \(x-1\),那我们不就可以选择 \([1,x-1]\) 作为答案了。

喜闻乐见的代码时间(

点击查看代码

#include<bits/stdc++.h>
#define fo(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define Ts template<typename Ty,typename... Ar>
#define Tp template<typename Ty>
#define isdigit(c) ((c)>='0'&&(c)<='9')
#define ll long long
#define RS register
#define gc getchar
#define pc putchar
#define I inline
using namespace std;
Tp I Ty wmax(Ty a,Ty b){return a>=b? a:b;}
Tp I Ty wmin(Ty a,Ty b){return a<=b? a:b;}
namespace WrongIO
{
	Tp I void read(Ty &x){x=0;Ty opt=1;char c=gc();while(!isdigit(c)&&c!='-')c=gc();if(c=='-')opt=-1,c=gc();while(isdigit(c))x=(x<<3)+(x<<1),x+=c-'0',c=gc();x*=opt;return;}
	Tp I void write(Ty x){short OI_USE[50],OI_top=0;if(x<=0) if(x==0)pc('0');else pc('-'),x*=-1;while(x)OI_USE[++OI_top]=x%10,x/=10;while(OI_top--)pc(OI_USE[OI_top+1]+'0');return;}
    I void writec(char c[]){int len=strlen(c);for(int i=0;i<len;i++)pc(c[i]);}
    I void writes(string s){int len=s.length();for(int i=0;i<len;i++)pc(s[i]);}
    I void readc(char &c,int l,int r){c=gc(); while(c!=EOF&&(c<l||c>r)) c=gc();}
    I void readc(char &c,char val){c=gc();while(c!=EOF&&c!=val) c=gc();}
    I void readc(char val){char c;c=gc();while(c!=EOF&&c!=val) c=gc();}
    I void readls(string &s){char c=gc();while(c!='\n') s.push_back(c),c=gc();}
    Ts I void read(Ty &x,Ar &...y) {read(x),read(y...);}
} using namespace WrongIO;
//这是祖传514年的板子,不用管(
ll T;
int main()
{
	cin>>T;
	while(T--)
	{
		ll n; cin>>n; ll i=1;
		for(;i<=100;i++)
		{
			if(n%i!=0) break;
		}
		write(i-1),pc('\n'); //i即为第一个不是n的因数的数
	}
	return 0;
}

如果样例解释的给出的区间也是 \([1,x-1]\) 就好了(

标签:val,Ty,题解,void,Interval,char,gc,区间,Divisors
From: https://www.cnblogs.com/JuyeScene/p/17591247.html

相关文章

  • Codeforces Round 889 (Div. 1) 题解
    A1.Dual(EasyVersion)https://codeforces.com/contest/1854/problem/A1题意给定一个长度为\(n\)的序列\(a_1,a_2,\dots,a_n\),你可以做以下操作:选定两个下标\(i,j(1\leqi,j\leqn)\),\(i,j\)可以相同,然后\(a_i\leftarrowa_{i}+a_j\)。要求构造一种操作......
  • HDU 1312 Red and Black 题解
    //注意边界判断,调了好久#include<iostream>#include<queue>usingnamespacestd;#definecheck(x,y)(x<wx&&x>=0&&y<hy&&y>=0)structnode{intx,y;};charroom[23][23];intn,m,wx,hy,num;intdir[4][2]={......
  • Xum题解
    Xum洛谷传送门题意:简化来说就是给你一个奇数\(x\),而你只能使用\(+\)或\(\bigoplus\),让你构造出一个包含\(1\)的数集。Analysis:首先为了得到\(1\),我们一般有两种思路,第一种是构造出\(n\)与\(n+1\)这种“出解情况”,这种思路考场寄掉了,先咕。那么来说说正解思路......
  • Sctf2023 Re 部分题解
    re是谁不复习计网和数据库写reSyclang给出两个文件一个是ir一个是编译器直接看ir即可拿vscode正则匹配替换relpace:(var\d+)\(@exp.([XLRXkey]+)(\[\d\])\)$1.$2$3#(\d+)$1<\+\d+>""(var\d+)\(@exp(.key\[\d+\])\)$1$2LABEL""GOTOgoto#!te......
  • 暑期竞赛配训 Day 1,本蒟蒻的第一篇题解qwq!
    洛谷P8725[蓝桥杯2020省AB3]画中漂流:-[1]读题:在梦境中,你踏上了一只木䇝,在江上漂流。根据对当地的了解,你知道在你下游D米处有一个峡谷,如果你向下游前进大于等于D米则必死无疑。现在你打响了急救电话,T秒后救援队会到达并将你救上岸。水流速度是1m/s,你现在有M点体力......
  • P9387 [THUPC 2023 决赛] 巧克力 题解
    这篇题解会只讲怎么dp,所以我们这里跳过博弈论的部分。Let'srephrasetheproblemstatementasfollows:给定\(n,m\),设\(x=1\oplus2\oplus\cdots\oplusn\oplusm\)。求有多少个有序三元组\((a,b,c)\)满足:\(a+b+c\len\)或\(a+b+c=m\)(如果都满足需要算两遍)。\((a+b......
  • Educational Codeforces Round 152 (Rated for Div. 2) 题解
    \(6\)题做出来\(3\)题,这一次的D题没能复刻上一次Round888Div.3最后几分钟AC的奇迹A.MorningSandwich大水题,5min时间4min都在翻译题面直接拿\(b\)和\(c+h\)进行比较分类讨论即可单次操作时间复杂度\(O(1)\)B.Monsters首先有一个特别显然、复杂度特别高的......
  • luogu P4069 [SDOI2016] 游戏 题解【李超树+树剖】
    目录题目描述解题思路code题目描述P4069[SDOI2016]游戏一棵树,树上有\(n\)个节点,最初每个节点上有\(1\)个数字:\(123456789123456789\)。有两种操作:\(\centerdot\)选择\(s,t\)两个节点,将路径上的每一个点都变多(\(1\)个变\(2\)个)数字:\(a\timesdis+b\),其中\(dis\)表示该节点......
  • P3979 遥远的国度 题解
    P3979遥远的国度题意一棵树,\(n\le10^5\),三个操作,\(m\le10^5\),点带权。换根路径推平子树查最小值思路如果没有换根,操作2,3是裸的树剖,考虑换根后的询问如何处理。显然不能再做一遍树剖,只能假装我们换根了,询问可以分成四种情况,令原根为\(root\),新根为\(id\),查询点......
  • luogu P3733 [HAOI2017] 八纵八横 题解【线段树分治+线性基+可撤销并查集+bitset】
    目录题目大意解题思路code题目大意题目链接给出一张\(n\)个点\(m\)条边的连通无向图,边带边权\(w_i\)。有以下三种操作,共\(q\)次:\(\centerdot\)在点\(x,y\)之间加入一条边权为\(w_i\)的边,如果这是第\(i\)个此种操作,则记这条新边为第\(i\)条。\(\centerdot\)将第\(k......