uva/12619.cpp at master · ming5656/uva · GitHub

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <cstdio>
#include <cstring>
#define ll long long
#define P  1000000007
using namespace std;

ll ns(0);
ll res;
int pos[1000005],num,prime[100000];
bool isPrime[1000005];
void sieve()
{
    memset(isPrime,1,sizeof(isPrime));
    memset(pos,0,sizeof(pos));
    isPrime[0]=isPrime[1]=false;
    for(int i=2; i<1000005; i++)
    {
        if(isPrime[i])
        {
            pos[i]=ns;
            prime[ns++]=i;
            for(int j=i*2; j<1000005; j+=i)
            {
                isPrime[j]=false;
            }
        }
    }
}
ll inverse_module(ll s)
{
    ll r=P-2,ans(1),c=s;
    while(r>0)
    {
        if(r&1)
        {
            ans=(ans*c)%P;
        }
        c=(c*c)%P;
        r>>=1;
    }
    return ans;
}

int main()
{
    int t,kase(0);
    int n;
    scanf("%d",&t);
    sieve();
    while(t--)
    {
        ll cnt[100000]= {};
        res=1;;
        scanf("%d",&n);
        ll total(0);
        while(n--)
        {
            scanf("%d",&num);
            if(num<0)
            {
                num=-num;
                int pp;
                for(int i=0; i<ns&&num>=prime[i]&&!isPrime[num]; i++)
                {
                    if(num%prime[i]==0)
                    {
                        ll d(0);
                        while(num%prime[i]==0)
                        {
                            d++;
                            num/=prime[i];
                        }
                        res=((res*((cnt[i]-d+1)%P)%P)*(inverse_module(cnt[i]+1)%P))%P;
                        cnt[i]-=d;
                    }
                }
                pp=pos[num];
                if(isPrime[num])
                {
                    res=((res*((cnt[pp])%P)%P)*(inverse_module(cnt[pp]+1)%P))%P;
                    cnt[pp]--;
                }
            }
            else
            {
                int pp;
                for(int i=0; i<ns&&num>=prime[i]&&!isPrime[num]; i++)
                {
                    if(num%prime[i]==0)
                    {
                        ll d(0);
                        while(num%prime[i]==0)
                        {
                            d++;
                            num/=prime[i];
                        }
                        res=((res*((cnt[i]+d+1)%P)%P)*((inverse_module(cnt[i]+1))%P))%P;
                        cnt[i]+=d;
                    }
                }
                pp=pos[num];
                if(isPrime[num])
                {
                    res=((res*((cnt[pp]+2)%P)%P)*(inverse_module(cnt[pp]+1)%P))%P;
                    cnt[pp]++;
                }
            }
            total+=res;
            total%=P;
        }
        printf("Case %d: %llu\n",++kase,total);
    }
    return 0;
}