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
| #include <bits/stdc++.h>
using namespace std; const int maxn = 1e5 + 10; const int maxS = 80;
int N, MOD[maxn]; char s[maxn]; struct get_MOD { int value[maxS + 5];
bool operator < (const get_MOD&b) const { for (int i = 1; i <= maxS; ++i) if (value[i] != b.value[i]) return value[i] < b.value[i]; return false; } }a[maxn]; map<get_MOD , int> pc; const int E9 = 1e9; void init() { for (int i = 1; i <= maxS; ++i) { MOD[i] = E9 + ((long long)rand() * rand() % E9); } } void input(get_MOD &a, int x) { for (int i = 1; i <= maxS; ++i) { a.value[i] = (((long long)a.value[i] * 10) + x) % MOD[i]; } } get_MOD mul(get_MOD &a, get_MOD &b) { get_MOD X; for (int i = 1; i <= maxS; ++i) { X.value[i] = (long long)a.value[i] * b.value[i] % MOD[i]; } return X; } int main() { srand(rand()); init(); scanf("%d", &N);
for (int i = 1; i <= N; ++i) { scanf("%s", s); int g = strlen(s); for (int j = 0; j < g; ++j) { input(a[i], s[j] - '0'); } pc[a[i]]++; } int ans = 0; for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { get_MOD temp = mul(a[i], a[j]); if (pc.count(temp)) ans += pc[temp]; } } printf("%d", ans); return 0; }
|