By

文章目录
  1. 1. 题意
  2. 2. 分析

原题

题意

给定n个数列，给你一个k，问从每个数列中取一个数，这些数的和，满足mod k不等于0，且这个和的值最大为多少？

分析

首先：这个数列给出x_0,a,b,c四个参数，有$$x_{n+1}=(ax_n+b)\%c$$定会形成循环节，但要注意的是*这个循环节可能前几个数值不在循环节的数以内，所以需要标记一下。
先暴力把每个数列能够获得的值都求出来。存下每个数列的最大值，和一个和最大值%K不相等的次大值。接下来先取每个序列最大的值，如果%K不为0则为答案。否则把其中一个换成次优值。因为前面满足%K不相等所以只用换一个。

我们可以不存次大值，只存n个数列中满足条件的次大值和最大值的差值就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
#define MAXN 1000007
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
struct node{
    int num,xx;
    bool operator < (const node& a)const{
        return xx>a.xx;
    }
}x[1007],ans[10007];
struct nnode{
    int num,xx,nnum;
};
nnode minm;
bool p[1007];
int main()
{
    //freopen("generators.in","r",stdin);
    //freopen("generators.out","w",stdout);
    int n,k,a,b,c;
    while(scanf("%d%d",&n,&k)!=EOF){
        memset(ans,0,sizeof(ans));
        minm.xx=INF;
        minm.num=-1;
        minm.nnum=-1;
        for(int i=0;i<n;i++){
            memset(x,0,sizeof(x));
            memset(p,false,sizeof(p));
            scanf("%d%d%d%d",&x[0].xx,&a,&b,&c);
            int m=0;
            x[0].num=0;
            p[x[0].xx]=true;
            while(!p[(a*x[m].xx+b)%c]){//找循环节不能是和第一个相同就停止寻找，因为可能前几个数值不在循环节的数以内
                m++;
                x[m].num=m;
                x[m].xx=(a*x[m-1].xx+b)%c;
                p[x[m].xx]=true;
            }
            m++;
            sort(x,x+m);
            ans[i]=x[0];
            int now=x[0].xx%k;
            for(int j=0;j<m;j++){
                if(x[j].xx%k!=now){
                    if(x[0].xx-x[j].xx<minm.xx){
                        minm.num=x[j].num;
                        minm.nnum=i;
                        minm.xx=x[0].xx-x[j].xx;
                    }
                    break;
                }
            }
        }
        int aans=0;
        for(int i=0;i<n;i++){
            aans+=ans[i].xx;
        }
        if(aans%k==0&&minm.xx==INF){
            printf("-1\n");
            continue;
        }
        if(aans%k==0){
            aans-=minm.xx;
            ans[minm.nnum].num=minm.num;
        }
        printf("%d\n",aans);
        printf("%d",ans[0].num);
        for(int i=1;i<n;i++){
            printf(" %d",ans[i].num);
        }
        printf("\n");
    }
}
文章目录
  1. 1. 题意
  2. 2. 分析