舟山网站开发,免费com域名网站,西安专业网站排名优化,网站怎么做端口映射大意: 给定序列, 求多少个区间积被k整除. 整除信息满足单调性, 显然双指针. 具体实现只需要考虑k的素数向量, 对每一维维护个指针即可. 这题看了下cf其他人的做法, 发现可以直接暴力, 若当前的前缀积模k为0, 暴力向前求出第一个后缀积为0的位置即可, 复杂度是$O(n)$的并且相当好… 大意: 给定序列, 求多少个区间积被k整除. 整除信息满足单调性, 显然双指针. 具体实现只需要考虑k的素数向量, 对每一维维护个指针即可. 这题看了下cf其他人的做法, 发现可以直接暴力, 若当前的前缀积模k为0, 暴力向前求出第一个后缀积为0的位置即可, 复杂度是$O(n)$的并且相当好写. #include iostream
#include algorithm
#include cstdio
#include math.h
#include set
#include map
#include queue
#include string
#include string.h
#include bitset
#define REP(i,a,n) for(int ia;in;i)
#define PER(i,a,n) for(int in;ia;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o1)
#define rc (lc|1)
#define mid ((lr)1)
#define ls lc,l,mid
#define rs rc,mid1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl \n
#define DB(a) ({REP(__i,1,n) couta[__i] ;hr;})
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int P 1e97, INF 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r1%P;for (a%P;n;aa*a%P,n1)if(n1)rr*a%P;return r;}
ll inv(ll x){return x1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x0;char pgetchar();while(p0||p9)pgetchar();while(p0p9)xx*10p-0,pgetchar();return x;}
//head#ifdef ONLINE_JUDGE
const int N 1e610;
#else
const int N 111;
#endifint n, k;
int p[11], f[11], cnt;
int g[N][11], cur[11], sum[11];int main() {scanf(%d%d, n, k);int mx sqrt(k0.5);REP(i,2,mx) if (k%i0) {p[cnt] i;while (k%i0) k/i,f[cnt];}if (k1) p[cnt]k,f[cnt];REP(j,1,n) { scanf(%d, k);REP(i,1,cnt) if (k%p[i]0) {while (k%p[i]0) g[j][i],k/p[i];}}ll ans 0;int now 0;REP(i,1,n) {REP(j,1,cnt) {while (cur[j]nsum[j]f[j]) sum[j]g[cur[j]][j];if (sum[j]f[j]) {printf(%lld\n, ans);return 0;}now max(now, cur[j]);}now max(now, i);ans n-now1;REP(j,1,cnt) sum[j]-g[i][j];}printf(%lld\n, ans);
}转载于:https://www.cnblogs.com/uid001/p/10715004.html
