Calculer la somme modulo m
Les opérations sur une carte graphique (GPU) offrent un très haut degré de parallélisme. Autrement dit, si on peut exécuter simultanément le même type de traitement sur de nombreux nombres, cela sera plus rapide que d’effectuer des opérations de types différents. L’équipe est en train de tester son code et vous demande d’écrire un programme pour vérifier la validité d’une addition de plusieurs nombres selon différents modulos.
On vous fournit deux listes d’entiers et . Vous devez calculer la somme de chaque paire et prise modulo :
Notez que différentes langues implémentent l’opération modulo de manière distincte. Par exemple, Python garantit toujours un résultat positif. En revanche, des langages comme C++ peuvent donner un résultat négatif après un modulo (-3 % 2 → -1). Une astuce très répandue consiste à ajouter le modulo
m au résultat si celui-ci est négatif, grâce à un if. Une approche plus générique est d’ajouter m puis de prendre à nouveau le modulo : ((a % m) + m) % m. Ainsi, le résultat est toujours positif.Entrée
La première ligne de l’entrée contient un unique entier
n (1 ≤ n ≤ 100 000), représentant le nombre d’éléments.La deuxième ligne contient
n entiers séparés par des espaces : ( ≤ ≤ ).La ligne suivante contient
n entiers séparés par des espaces : ( ≤ ≤ ).La dernière ligne contient
n entiers séparés par des espaces : (1 ≤ ≤ ).Sortie
Le programme doit afficher
n entiers séparés par des espaces, correspondant à .Exemples
Entrée | Sortie |
3
1 2 1
3 4 1
2 5 3 | 0 1 2 |
Explication
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB