首页 > 其他分享 >818E - Card Game Again 双指针+分解质因数

818E - Card Game Again 双指针+分解质因数

时间:2022-11-10 23:22:51浏览次数:60  
标签:Again ++ else int Game maxn mp 818E st

题意:

有多少种 x y 的选择方法,使得对于长度为 n 的 a 数组, 取  a[x+1] ,a[x+2] ... a[y-2] , a[y-1] 的乘积是 k 的倍数 

思路:

对于所有的 x ,当选择 x = x + 1 时 y = y  满足条件 ,则此时取 x = x ,y = y 也满足条件 。所以可以用双指针

只要 x  到 y 之间的所有数的乘积的 因子的个数 大于等于 k 的所有因子的个数就满足条件, 此时对于所有 y >= y 的情况也都满足条件 

由于 数据是 1e9,所以如果某个因子大于 根号1e9,它就是这个数本身,这个数是个质数, 且在k中最多只会出现一次,所以可以存到一个set里

//#define int ll
const int N = 2e5+10,maxn = 3e4 + 2e3;
int n,k;
int is[maxn];
V<int>prime;
void init() {
    fo(i,2,maxn-1) {
        if(!is[i]) {
            prime.pb(i);
            for(ll j = 1ll * i * i; j < maxn;j += i) {
                is[j] = 1;
            }
        }
    }
}
int a[N];
struct nd {
    int x,cnt;
};
V<nd> getFactor(int x) {
    V<nd> v;
    for(int i = 0;1ll * prime[i] * prime[i] <= x;i ++ ) {
        int c = 0;
        while(x % prime[i] == 0) {
            x /= prime[i];
            c ++ ;
        }
        if(c) v.pb(nd{prime[i],c});
    }
    if(x > 1) v.pb(nd{x,1});
    return v;
}
map<int,V<nd>> mp;
int C[maxn];
set<int> st;
void solve()
{
    init();
    cin>>n>>k;
    fo(i,0,n-1) {
        cin>>a[i];
    }
    int l = 0,r = 0;
    V<nd> K = getFactor(k);
    ll ans = 0;
    int state = 1;
    while(l < n && r < n) {
        V<nd> X;
        if(state) {
            if(!mp.count(a[r])) mp[a[r]] = getFactor(a[r]);
            X = mp[a[r]];
            for(int i = 0;i < X.size();i ++ ) {
                if(X[i].x > maxn) st.insert(X[i].x); //如果x 比  
                else C[X[i].x] += X[i].cnt;
            }
        } else {
            if(!mp.count(a[l])) mp[a[l]] = getFactor(a[l]);
            X = mp[a[l]];
            for(int i = 0;i < X.size();i ++ ) {
                if(X[i].x >maxn) st.erase(X[i].x); // 如果 
                else C[X[i].x] -= X[i].cnt;
            }
            l ++ ;
        }
        int flg = 0;
        for(int i = 0;i < K.size();i ++ ) {
            if(K[i].x >maxn) { // 如果 k 的这个因子大小比 maxn 大 
                if(!st.count(K[i].x)) {// 如果st 中不包括这个因子 
                    flg = 1;break;
                }
            } else if(K[i].cnt > C[K[i].x]) { // 如果因子少,flg = 1 
                flg = 1;break;// K是k 中的因子 , 
            }
        }
        if(flg) { // 失败了就往右边找 
            r ++ ;
            state = 1;
        } else {
            ans += n - r;
            if(l == r) {
                l ++ ;r ++ ;state = 1;ms(C,0);st.clear();
            } else state = 0;
        } 
    }
    cout<<ans<<endl;
     rt;
} 

 

标签:Again,++,else,int,Game,maxn,mp,818E,st
From: https://www.cnblogs.com/er007/p/16879202.html

相关文章

  • unreal engine 5 移动到其它主机时的 epic games launcher 识别修复
    unrealengine5 安装后移动到其它主机,epicgameslauncher 不能主动识别。关键配置文件为:epicgameslauncher 的manifests文件。该文件位于 C:\ProgramFiles(x86......
  • HDU 2216 Game III
    ProblemDescriptionZjtandSarawilltakepartinagame,namedGameIII.ZjtandSarawillbeinamaze,andZjtmustfindSara.Therearesomestrang......
  • HDU 1329 Hanoi Tower Troubles Again!
    DescriptionPeoplestoppedmovingdiscsfrompegtopegaftertheyknowthenumberofstepsneededtocompletetheentiretask.Butontheotherhand,they......
  • HUST 1374 Just Another Game
    DescriptionHHandLLalwaysplaygamestogether,however,LLwoneverytime~~.ThatmakeHHveryunhappy,sothistimeHHisdesigninganewgameforbeat......
  • HDU 5591 ZYB's Game
    ProblemDescription withhisclassmatesinhiking:ahostkeepsanumberin  loses,orthehostwilltellalltheplayersthatthenumbernowisbigger......
  • 安装Pygame
    安装:在Windows命令框中输入:pipinstallpygame安装成功2.1.2版本  检查版本:python-mpygame--version  over~......
  • Codeforces Round #721 (Div. 2) B2. Palindrome Game (hard version)
    ​​传送门​​Theonlydifferencebetweentheeasyandhardversionsisthatthegivenstringsintheeasyversionisinitiallyapalindrome,thisconditioni......
  • 杭电9-Just another board game
    ​​传送门​​题意:给你一个的网格,每个格子里有其相应的权重,最初有一个棋子在上,棋子最终所在的位置为最终值,a想要最大化这个值,b要最小化这个值。思路:从整场比赛来看,如果某人......
  • 45. Jump Game II
    Youaregivena 0-indexed arrayofintegers nums oflength n.Youareinitiallypositionedat nums[0].Eachelement nums[i] representsthemaximumleng......
  • 55. Jump Game
    Youaregivenanintegerarray nums.Youareinitiallypositionedatthearray's firstindex,andeachelementinthearrayrepresentsyourmaximumjumpleng......