南通网站建设费用,网站做seo屏蔽搜索,网站建设服务合同缴纳印花税吗,亚马逊ec2搭建WordpressCodeforces Round #717 (Div. 2) D 题意:n个数 q个询问#xff0c;每一个询问有l和r#xff0c;问你l到r这段区间中最少能分成几段#xff0c;每一段中的数都是互质的。 思路#xff1a;首先预处理出每一个点向左走最多能走多远#xff0c;可以分解质因数来找#xff0c…Codeforces Round #717 (Div. 2) D 题意:n个数 q个询问每一个询问有l和r问你l到r这段区间中最少能分成几段每一段中的数都是互质的。 思路首先预处理出每一个点向左走最多能走多远可以分解质因数来找记录质因数最右边的位置然后使用倍增dpdp【i】【j】代表j点向左走i^2步 最远能走到哪然后循问的时候 也是倍增处理就好了。
#includebits/stdc.h
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define rep(i,s,n) for(int is;(i)(n);i)
#define rep1(i,s,n) for(int is;(i)(n);i--)
#define se second
#define scd(a) scanf(%d,a)
#define scdd(a,b) scanf(%d%d,a,b)
#define scddd(a,b,c) scanf(%d%d%d,a,b,c)
#define ac coutans\n
#define F(x) ((x)/3((x)%31?0:tb))
#define G(x) ((x)tb?(x)*31:((x)-tb)*32)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairll,ll pii;
int dx[4] {-1,0,1,0},dy[4] {0,-1,0,1};
const ll mod1e97;
const ll N 1e510;
const double eps 1e-4;
//const double piacos(-1);
int last[N];
int vis[N];
ll dp[22][N];
int main()
{iosint n,q;cinnq;rep(i,1,n) {int x;cinx;last[i]last[i-1];for(int j2;j*jx;j){if(x%j0){last[i]max(vis[j],last[i]);while(x%j0) x/j;vis[j]i;}}if(x!1){last[i]max(vis[x],last[i]);vis[x]i;}}for(int i1;in;i) dp[0][i]last[i];for(int i1;i20;i){for(int j1;jn;j){dp[i][j]dp[i-1][dp[i-1][j]];}}while(q--){int l,r;cinlr;ll ans0;for(int i19;i0;i--){if(ldp[i][r]){ans(1lli);rdp[i][r];}}coutans1endl;}return 0;
}
