A Adrien and Austin

写了几组数据试了一下，发现毫无进展。

唯一有用的地方就是，取中间更好，而且感觉adrien这个人输不了。

猜他不会输，特判n==0和k==1的情况。

蒙过了。

正解的思路大概是这样：

当k不等于1，那么我adrien每次取中间的段落，使之划分为等长的两段。

austin每次在一段干什么，我就在另一段干相同的事情。

然后austin最后一步取完了，我adrien也最后一步取完了。

然后austin就输了。

int n,k;
int main(){
    scanf("%d%d",&n,&k);
    if(n==0){
        printf("Austin
");
    }
    else if(k==1){
        if(n&1){
            printf("Adrien
");
        }
        else{
            printf("Austin
");
        }
    }
    else{
        printf("Adrien
");    
    }
    return 0;
}

I Magic Potion

题目是这样的，n个奥特曼，m只怪兽，k瓶药。

一般一个奥特曼一次只能干一只怪兽。但是磕了药的奥特曼能一次干两只。（体力增加了++!)

问奥特曼最多能干几只怪兽。

看起来就很像是网络流。

第一种想法，能干掉的奥特曼--怪兽建边。

力量源泉（源点）连奥特曼，边的限制为1，让每一个奥特曼都只能干一只怪兽，统计人员（汇点）连怪兽。

药水呢？药水相当于是另外一个力量源泉（源点），所以源点连药水，边的限制为k，药水连每个奥特曼。

第二种想法，假如没有药水了被ban了

那么，我按上面的方式建一个图，跑出来得到每个奥特曼只能干一只怪兽的最大数量。记作a

再建一个每个奥特曼有能力干两只怪兽的最大数量。记作b

如果a+k>=b，说明此时怪兽不够奥特曼们干的，那么最大数量就是b(相当于有些奥特曼只吃药，不干活）

如果a+k<b，说明怪兽太多了，即使一部分奥特曼磕了药也干不完，那么最大数量就是a+k

//为了排版就不放dinic的部分了

int main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=n;++i){
        scanf("%lld",&mm);
        for(int j=1;j<=mm;++j){
            scanf("%lld",&y);
            add(i,y+n,1);add(y+n,i,0);
        }
    }
    s=n+m+1;t=n+m+2,zz=n+m+3;
    for(int i=1;i<=n;++i){
        add(i,s,0);
        add(s,i,1);
        add(zz,i,1);
        add(i,zz,0);
    }
    for(int i=1;i<=m;++i){
        add(i+n,t,1);
        add(t,i+n,0);
    }
    add(s,zz,k);
    dinic();
    printf("%lld
",maxflow);
    return 0;
}

J. Prime Game

很难想象我还是摸出来了

话说因为分解质因数没写好，T了好久，人好菜啊，还是找了一下模板才知道怎么改的

题意：对于每一个子区间，求他子区间乘积的素因数的个数，然后所有子区间相加。

也就是说，比如一个ai是6，那么经过他的子区间的乘积，一定能拆出2和3。

那么这个ai他对所有经过他的子区间都共贡献了一个2，一个3。

然后我们计算每个点的素因数的对子区间的贡献就好啦！

看起来很简单，但是贡献不能被重复计算。

如果一个区间中的素因数的已经有2了，那么区间扩大一点，再进来一个2也不会发生改变。

比如a2的素因子2，而且他前面没有素因数2

那么他能贡献的区间有[1,2]，[1,3]，……，[1,10]and[2,2]，[2,3]，……，[2,10]（假设有n==10）

对这些区间我们看一看，发现区间的个数就是左右端点的数量相乘。

此时假设下一个素因数2，出现在了a5，
那么他能贡献的区间有[1,5]，[1,6]，……，[1,10]

　　　　　　　　and[2,5]，[2,6]，……，[2,10]
　　　　　　　　and[3,5]，[3,6]，……，[3,10]
　　　　　　　　and[4,5]，[4,6]，……，[4,10]

　　　　　　　　and[5,5]，[5,6]，……，[5,10]（假设有n==10）

我们发现了一些问题，[1,5]，[1,6]，……，[1,10]已经计算了素因数2的贡献了，

再看一下，[2,5]，[2,6]，……，[2,10]也计算过了。

右移左端点，[3,5]，[3,6]，……，[3,10]开始就没有重复计算了。

也就是说左端点的数量等于（i当前2的位置，j上一个2的位置）（i-j）

　　　　右端点的数量等于（n-i+1）（一路往右取，会影响之后吗？会，但是我们删去重复是在之后对左操作，往右就是该取满的）

const ll N=1e6+7;
int n,a[N],idx,tmp;//记录素数数组用到哪里 
vector<ll> q[N];//素数数组

bool isPrime[N];
int Prime[N],cnt=0;
void GetPrime(int n){
    memset(isPrime, 1, sizeof(isPrime));
    isPrime[1] = 0;
    for(int i = 2; i <= n; i++){
        if(isPrime[i])
            Prime[++cnt] = i;
        for(int j = 1; j <= cnt && i*Prime[j] <= n/*不超上限*/; j++) {
            isPrime[i*Prime[j]] = 0;
            if(i % Prime[j] == 0)    break;
        }
    }
}
int main(){
    scanf("%d",&n);
    GetPrime(N);
    for(int i=0;i<N;++i){
        q[i].push_back(0); 
    }
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;++i){//分解 
        tmp=a[i];
        //cout<<"tmp=="<<tmp<<"
";
        if(isPrime[tmp]){
            //cout<<"tmp"<<tmp<<"
";
            q[tmp].push_back(i);//记录位置 
        }
        else{
            for(int j=1;Prime[j]*Prime[j]<=a[i]&&j<=cnt;++j){
                if(tmp%Prime[j]==0){
                    q[Prime[j]].push_back(i);//记录位置 
                    while(tmp%Prime[j]==0)    tmp/=Prime[j]; 
                }
            }
            if(tmp>1)    q[tmp].push_back(i);
        }
    }
    ll ans=0;int siz;
    for(int i=1;i<=cnt;++i){//计算
        siz=q[Prime[i]].size();
        for(int j=1;j<siz;++j){
            ans=ans+1ll*(q[Prime[i]][j]-q[Prime[i]][j-1])*(n-q[Prime[i]][j]+1);
        }
    } 
    cout<<ans<<"
";
    return 0;
}